aboutsummaryrefslogtreecommitdiff
path: root/triangle.cpp
blob: d7e826b721ec342835d669b98af38d7984a3f108 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include "leetcode.h"

class Solution {
public:
  int minimumTotal(vector<vector<int>> &triangle) {
    vector<int> ans(triangle.size(), triangle[0][0]);
    for (int i = 1; i < triangle.size(); i++)
      for (int j = i; j >= 0; j--) {
        if (j == 0)
          ans[0] += triangle[i][j];
        else if (j == i)
          ans[j] = triangle[i][j] + ans[j - 1];
        else
          ans[j] = triangle[i][j] + min(ans[j - 1], ans[j]);
      }
    return *min_element(ans.begin(), ans.end());
  }
};

int main() {}