C++ DP solution, O(n) space complexity


  • 0
    H
    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            int m = triangle.size();
            vector<int> dp(m, INT_MAX);
            dp[0] = triangle[0][0];
            for(int i = 1; i < m; i ++) {
                for(int j = i; j >= 0; j --) {
                    int idx_l = max(0, j-1);
                    int idx_r = min(j, i-1);
                    dp[j] = triangle[i][j] + min(dp[idx_l], dp[idx_r]);
                }
            }
            int ans = INT_MAX;
            for(int i : dp) ans = min(ans, i);
            return ans;
        }
    };
    

Log in to reply
 

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