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

  • 0

    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 {
        int helper(vector<vector<int>>& tri, int index, int ht, vector<int> &memo)
                return (tri[ht][index]);
            int L=0;
                L= helper(tri, index, ht+1, memo);        
                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.