C++ using DP no extra space,11ms,5 code lines


  • 2
    K
    class Solution {
    public:
    	int minimumTotal(vector<vector<int> > &triangle) {
    		int cur=triangle.size()-2;
    		for(;cur>=0;cur--)
    			for(int i=0;i<=cur;i++)
    				triangle[cur][i]=min(triangle[cur+1][i],triangle[cur+1][i+1])+triangle[cur][i];
    		return triangle[0][0];
    	}
    };

Log in to reply
 

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