Problem: https://leetcode.com/problems/triangle/description/

Accepted Code

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
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int m=triangle.size();
        int n=triangle[m-1].size();
        for(int i=1;i<m;i++) {
            triangle[i][0]+=triangle[i-1][0];
        }
        for(int i=1;i<n;i++) {
            triangle[i][i]+=triangle[i-1][i-1];
        }
        for(int i=2;i<m;i++) {
            for(int j=1;j<n&&j<i;j++) {
                triangle[i][j]+=min(triangle[i-1][j],triangle[i-1][j-1]);
            }
        }

        int ans=triangle[m-1][0];
        for(int i=1;i<n;i++) {
            if(triangle[m-1][i]<ans) {
                ans=triangle[m-1][i];
            }
        }
        return ans;
    }
};