C++, 6ms, O(n) time and space. DP top-down.


  • 0
    V

    As other solutions state, bottom-up does make the job easier in this question. But I tried top-down with a smart way of storing the overlapping branches using DP. Works good!

    class Solution {
    public:
        int helper(vector<vector<int>>& tri, int index, int ht, vector<int> &memo)
        {        
            if(ht==tri.size()-1)
                return (tri[ht][index]);
            
            int L=0;
            if(memo[ht+1]==0)                   
                L= helper(tri, index, ht+1, memo);        
            else
                L=memo[ht+1];   //reuse the last calculated right child, saving time
                
            int R= helper(tri, index+1, ht+1, memo);
            memo[ht+1]=R;   //update the right child for this level, so adjacent can use this as its left
            
            return(min(L,R) + tri[ht][index]);
        }
        
        int minimumTotal(vector<vector<int>>& triangle) {
            
            vector<int> memo(triangle.size(),0);        
            return(helper(triangle, 0, 0, memo));
        }
    };
    

Log in to reply
 

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