DP Python Solution


  • 1
    B
    class Solution:
        # @param triangle, a list of lists of integers
        # @return an integer
        
        def minimumTotal(self, triangle):
            R = len(triangle)
            for i in range(R)[::-1]:
                if i == R-1:
                    m = triangle[R-1]
                else:
                    for j in range(i+1):
                        m[j] = triangle[i][j] + min(m[j], m[j+1])
            
            return m[0]

  • 0
    R

    c++ DP solution (12ms)

    int minimumTotal(vector<vector<int> > &triangle) {       
            int n = triangle.size();
            if(n == 0)
                return 0;
            int sum=triangle[0][0], id=0, left, right;
            vector<int> store; //array to store min values (bottom up manner)
            //store the leaves in the array
            for(int i=0; i<n; i++) {
                store.push_back(triangle[n-1][i]);
            }
            for(int i=n-2; i>=0; i--) {
                for(id=0; id<=i; id++) {
                    left = triangle[i][id] + store[id];
                    right = triangle[i][id] + store[id+1];
                    // update store array (ignore end values)
                    if(left<right)
                        store[id] = left;
                    else
                        store[id] = right;
                }
            }
            return store[0]; //result will be first element
            
        }

Log in to reply
 

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