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:
Post a Comment