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.c | |
parent | ff0500a7e8c426a0a6f46076761869fc88098d87 (diff) | |
download | leetcode-afadd0bbf56f8aff8c5b397df08731c750302fd4.tar.gz leetcode-afadd0bbf56f8aff8c5b397df08731c750302fd4.zip |
120. triangle
Diffstat (limited to 'triangle.c')
-rw-r--r-- | triangle.c | 38 |
1 files changed, 38 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); +} |