Simple C++ solution. No extra space.


  • 1
    F

    The idea is to simply use the triangle itself as your DP table.

    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            if(!triangle.size()) return 0;
            if(triangle.size()==1) return triangle[0][0];
            int levels = triangle.size();
            for(int l = levels-2;l>=0;l--){
                for(int j=0;j<=l;j++){
                    triangle[l][j] = min(triangle[l+1][j],triangle[l+1][j+1]) + triangle[l][j];
                }
            }
            return triangle[0][0];
        }
    };
    

Log in to reply
 

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