diff options
-rw-r--r-- | triangle.c | 38 | ||||
-rw-r--r-- | triangle.py | 31 |
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]])) |