Problem

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Example

Given the following triangle ::
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

JavaScript Code

function minimumTotal(triangle) {
     
    var total = [];
    var l = triangle.length - 1;
 
    for (var i = 0; i < triangle[l].length; i++) {
        total.push(triangle[l][i]);
    }
 
    // iterate from last second row
    for (var i = triangle.length - 2; i >= 0; i--) {
        for (var j = 0; j < triangle[i + 1].length - 1; j++) {
            total[j] = triangle[i][j] + Math.min(total[j], total[j + 1]);
        }
    }
 
    return total[0];
 }
var kk = [
          [2],
          [3,4],
          [6,5,7],
          [4,1,8,3]
         ];
console.log(minimumTotal(kk));

0 comments:

Blogroll

Follow this blog by Email

Popular Posts