aboutsummaryrefslogtreecommitdiff
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
parentff0500a7e8c426a0a6f46076761869fc88098d87 (diff)
downloadleetcode-afadd0bbf56f8aff8c5b397df08731c750302fd4.tar.gz
leetcode-afadd0bbf56f8aff8c5b397df08731c750302fd4.zip
120. triangle
-rw-r--r--triangle.c38
-rw-r--r--triangle.py31
2 files changed, 69 insertions, 0 deletions
diff --git a/triangle.c b/triangle.c
new file mode 100644
index 0000000..f283536
--- /dev/null
+++ b/triangle.c
@@ -0,0 +1,38 @@
+// 120. Triangle
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+int minimumTotal(int **triangle, int triangleSize, int *triangleColSize) {
+ int prev = triangleColSize[triangleSize - 1];
+ int *memo = (int *)malloc(prev * sizeof(int));
+ for (int i = 0; i < prev; ++i)
+ memo[i] = triangle[triangleSize - 1][i];
+ for (int r = triangleSize - 2; r >= 0; --r)
+ for (int c = 0; c < triangleColSize[r]; ++c)
+ memo[c] = triangle[r][c] + fmin(memo[c], memo[c + 1]);
+ int ans = memo[0];
+ free(memo);
+ return ans;
+}
+
+int main() {
+ int t1i[4][4] = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}}, tcs1[] = {};
+ int t2i[1][1] = {{-10}};
+ for (int i = 0; i < ARRAY_SIZE(t1i); i++)
+ tcs1[i] = ARRAY_SIZE(t1i[0]);
+ struct two_d_arr *t1 =
+ two_d_arr_init(ARRAY_SIZE(t1i), ARRAY_SIZE(t1i[3]), t1i);
+ struct two_d_arr *t2 =
+ two_d_arr_init(ARRAY_SIZE(t2i), ARRAY_SIZE(t2i[0]), t2i);
+ printf("%d\n", minimumTotal(t1->arr, t1->row_size, tcs1)); // expect: 11
+ printf("%d\n",
+ minimumTotal(t2->arr, t2->row_size, t2->col_size)); // expect: -10
+ two_d_arr_free(t1);
+ two_d_arr_free(t2);
+}
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]]))