1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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);
}
|