C++ DP Solution Runtime:8ms


  • 1
    P
    class Solution {
    public:
        int minimumTotal(vector<vector<int> > &triangle) {
            int m = triangle.size();
            int s[m];
            for(int i=0; i<m; i++)
                s[i] = triangle[m-1][i];
            for(int i=m-2;i>-1;i--)
            {
                for(int j=0; j<i+1; j++)
                    if(s[j]<s[j+1])
                        s[j] = s[j]+ triangle[i][j];
                    else
                        s[j] = s[j+1]+ triangle[i][j];
            }
            return s[0];
            
        }
    };

Log in to reply
 

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