Standard dynamic programming!


  • 0
    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
           int result=INT_MAX;
           vector<int> mintotal(triangle[triangle.size()-1].size());
              mintotal[0]=triangle[0][0];
              for(int i=1;i<triangle.size();i++)
                  for(int j=triangle[i].size()-1;j>=0;j--){       //start from right side ,otherwise left side have influence to the backward
                      if(j==0)
                          mintotal[j]=mintotal[j]+triangle[i][j];
                      else if(j==triangle[i].size()-1)
                          mintotal[j]=mintotal[j-1]+triangle[i][j];
                      else
                          mintotal[j]=min(mintotal[j],mintotal[j-1])+triangle[i][j];
                  }
           for(int i=0;i<mintotal.size();i++)
              result=min(mintotal[i],result);
           return result;
        }
    };

Log in to reply
 

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