120. Triangle

https://leetcode.com/problems/triangle/
从上到下：

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        if(n == 0) return 0;
        vector<vector<int> > dp(n,vector<int>(n,0));
        dp[0][0] = triangle[0][0];
        for(int i = 1; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                int l = j - 1 >= 0 ? dp[i-1][j-1] : INT_MAX;
                int r = j <= i - 1 ? dp[i-1][j] : INT_MAX;
                dp[i][j] = min(l,r) + triangle[i][j];
            }
        }
        int res = INT_MAX;
        for(int i = 0; i < n; i++)
            res = min(res, dp[n-1][i]);
        return res;
    }
};

从下到上：

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