A Detail explain for the solution, with javascript code.


  • 0
    S

    This subject has a very easy way to solve, which is do an DP research and find the shortest path, but it will spend O(N^2) space, which is not an optimized choice.
    So instead of starting from top to bottom, let's think it in a reverse direction, can we start from bottom?
    The answer is yes. Suppose we start from level n to n, the min path is the level itself, in the example given,
    if we start from level 4 to 4, use a number to mark the length we used, we find the result being min = [4,1,8,3].
    Then we go to level n-1, we start from [6,5,7] to [4,1,8,3],
    let's see if we go from first element in n-1, which is from 6 to the bottom, the min length it will use is: 6+min(4,1) = 7.
    now we have:

     [6,5,7]  min=[7.]
    [4,1,8,3] min=[4,1,8,3] // => It is OK to let min = [7, 1, 8 ,3], since in next step, we dont need 4 anymore.
    

    We could start dealing with 5, now we know that if we start from 5 to bottom, we have the min length as 5+min(1,8)=6.
    Now you find something? When we process the ith element in current level, we only care about i and (i+1)th element in min, so it doesn't matter if we replace the 4 with 7.
    After process the third level, now we have:

     [6,5,7]  min=[7, 6, 10, 3] //=> At this step, 3 is actually useless. In next step we only care about first three elements in min.
    [4,1,8,3]
    

    Let's keep the loop go until we reach the top, we could output min[0] as our result.

    /**
     * @param {number[][]} triangle
     * @return {number}
     */
    var minimumTotal = function(triangle) {
        let min = triangle[triangle.length-1];
        for(let i=triangle.length-2; i>=0; i--){
            let cur = triangle[i];
            for(let j=0; j<cur.length; j++){
                min[j] = Math.min(min[j+1], min[j]) + cur[j];
            }
        }
        return min[0];
    };

Log in to reply
 

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