一、原题
通过从下面的三角形的顶部开始并移至下面一行的相邻数字，从上到下的最大总数为23。
3
7 4
2 4 6
8 5 9 3
也就是说，3 + 7 + 4 + 9 = 23。
从下面的三角形的顶部到底部找到最大的总数：
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
注意：由于只有16384条路线，因此可以通过尝试每条路线来解决此问题。但是，问题67对于包含一百行的三角形是同样的挑战。它不能用蛮力解决，需要一个聪明的方法！; o）
二、解题思路
看到题目，首先想到的思路是遍历，但是遍历在行数很多情况下很慢，会导致运行不出结果；
分析题目，可以发现每一个节点只能走(i+1,j),(i+1)(j+1)两条路，故每一个节点的路径总和都与其前面两个节点有关，该路径想要是最大和，必然是与到达该节点的前面两个节点其中大的一个相加的；
因此，我们可以用一个二维数组保存每一个节点的最大值，这样，到最后一行的最大值就是最大的路径总和。
function maximumPathSumI(triangle) {var arr = [];var temp;for(var i=0;i<triangle.length;i++){var arr1 = [];for(var j=0;j<triangle[i].length;j++){arr1[j]=0;}arr[i] = arr1;}arr[0][0] = triangle[0][0];for(var i=1;i<arr.length;i++){for(var j=0;j<arr[i].length;j++){temp=0;arr[i][j] = triangle[i][j] + arr[i-1][j];if(j>0) temp=triangle[i][j] + arr[i-1][j-1];arr[i][j] = arr[i][j] > temp?arr[i][j]:temp;}}for(var i=0;i<arr[arr.length-1].length;i++){temp=temp>arr[arr.length-1][i]?temp:arr[arr.length-1][i];}console.log(temp);return temp;
}const testTriangle = [[3, 0, 0, 0],[7, 4, 0, 0],[2, 4, 6, 0],[8, 5, 9, 3]];maximumPathSumI(testTriangle);