Simple C++ solution. No extra space.

  • 1

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

    class Solution {
        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.