### 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