aboutsummaryrefslogtreecommitdiff
path: root/triangle.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-09-24 20:47:24 -0600
committerJack Sangdahl <[email protected]>2025-09-24 20:47:24 -0600
commitafadd0bbf56f8aff8c5b397df08731c750302fd4 (patch)
tree3845bad047ec123ee798c27199080cb84710aa62 /triangle.py
parentff0500a7e8c426a0a6f46076761869fc88098d87 (diff)
downloadleetcode-afadd0bbf56f8aff8c5b397df08731c750302fd4.tar.gz
leetcode-afadd0bbf56f8aff8c5b397df08731c750302fd4.zip
120. triangle
Diffstat (limited to 'triangle.py')
-rw-r--r--triangle.py31
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]]))