diff options
author | Jack Sangdahl <[email protected]> | 2025-09-24 20:47:24 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-24 20:47:24 -0600 |
commit | afadd0bbf56f8aff8c5b397df08731c750302fd4 (patch) | |
tree | 3845bad047ec123ee798c27199080cb84710aa62 /triangle.py | |
parent | ff0500a7e8c426a0a6f46076761869fc88098d87 (diff) | |
download | leetcode-afadd0bbf56f8aff8c5b397df08731c750302fd4.tar.gz leetcode-afadd0bbf56f8aff8c5b397df08731c750302fd4.zip |
120. triangle
Diffstat (limited to 'triangle.py')
-rw-r--r-- | triangle.py | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/triangle.py b/triangle.py new file mode 100644 index 0000000..c6af141 --- /dev/null +++ b/triangle.py @@ -0,0 +1,31 @@ +# 120. Triangle + +""" +given a 'triangle' array, return the minimum path sum from top to bottom. for +each step, you may move to an adjacent number of the row below. more +formally, if you are index 'i', on the current row, you may move to either +index 'i' or index 'i + 1' on the next row. +""" + + +class Solution(object): + def minimumTotal(self, triangle): + """ + :type triangle: List[List[int]] + :rtype: int + """ + + def dfs(r, c): + if r == len(triangle): + return 0 + l = triangle[r][c] + dfs(r + 1, c) + r = triangle[r][c] + dfs(r + 1, c + 1) + return min(l, r) + + return dfs(0, 0) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimumTotal(triangle=[[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]])) + print(obj.minimumTotal(triangle=[[-10]])) |