Here is my AC solution for this problem without using any extra space


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

  • 0
    C

    It's a smart way to reuse the space of vector triangle, but I don't think we are supposed to modify the input vector. And by the way, if you go through level by level from downside up, then one way round will be enough.


Log in to reply
 

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