DP using C++ (8ms) with O(n) extra space


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

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.