Elegant cpp solution with 8ms AC


  • 1
    X
    class Solution {
    public:
        int minimumTotal(vector<vector<int> > &triangle) {
    			if (triangle.size()<1) return 0;
    			vector<int> extra(triangle.size(),INT_MAX);
    			extra[0] = triangle[0][0];
    			for ( int i = 1; i<triangle.size(); ++i )
    			{
    				for ( int j = triangle[i].size()-1; j>=0; --j )
    				{
    					if ( j==0 )
    					{
    						extra[j] = triangle[i][j] + extra[0];
    					}
    					else
    					{
    						extra[j] = triangle[i][j] + std::min(extra[j-1], extra[j]);
    					}
    				}
    			}
    			int min_sum = extra[0];
    			for ( int i = 1; i < extra.size(); ++i ) min_sum = std::min(min_sum, extra[i]);
    			return min_sum;
        }
    };

Log in to reply
 

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