My O(n) cpp code using DP


  • 4
    C
    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) 
        {
            // s[r][c] = min(s[r+1][c], s[r+1][c+1])
            // s[r][c] = triangle[r][c] if r is the last row
            
            vector<int> minTotalVec(triangle.back());
            for(int i = triangle.size()-2; i >=0; i--)
                for(int j = 0; j <= i; j++)
                {
                    int sum1 = minTotalVec[j] + triangle[i][j];
                    int sum2 = minTotalVec[j+1] + triangle[i][j];
                    
                    minTotalVec[j] = std::min(sum1, sum2);
                }
                
            return minTotalVec[0];
        }
    };

Log in to reply
 

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