C++ O(1) solution


  • -1
    J
    class Solution {
    public:
       int minimumTotal(vector<vector<int> > &triangle) {
    	for (int i = 1; i<triangle.size(); i++)
    	{
    		for (int j = 0; j<triangle[i].size(); j++)
    		{
    			int num1 = INT_MAX, num2 = INT_MAX;
    			if (j > 0)
    				num1 = triangle[i - 1][j - 1];
    			if (j < triangle[i-1].size())
    				num2 = triangle[i - 1][j];
    
    			triangle[i][j] = triangle[i][j] + min(num1, num2);
    		}
    	}
    
    	return *min_element(triangle.back().begin(), triangle.back().end());
      }
    };

Log in to reply
 

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