aboutsummaryrefslogtreecommitdiff
path: root/triangle.c
blob: f283536c3ab5632427405e66e17212a69b3070be (plain)
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);
}