问题
从下面的三角形的顶至底，只能在下一行相邻的数字间选择移动，得出最大的从顶至底的和为23。
3 7 4 2 4 6 8 5 9 3
因为：3 + 7 + 4 + 9 = 23。
请找出在triangle.txt（右键“保存链接/目标为…”）里面的最大的从顶至底的和，这个文本文件是一个15KB大、包含100行的三角形。
注意：这和问题18是同一个问题，但是困难很多。因为是不可能使用暴力算法遍历所有路径的，所有路径的总数高达\(2^{99}\)！如果你的计算机可以在1秒内遍历\(10^{12}\)个路径，这需要120亿年才可以遍历所有路径。有高效的算法可以解决这个问题的！😉
* 传送门
分析
既然和《欧拉计划问题18》是同一个问题，那么就用前面使用过的、从底至顶的『春卷算法』！
答案
// answer: bottom up
const $ = jQuery
$.get('/_x_.php?' + $('#p067_triangle').attr('href'), (txt) => {
const start = Date.now()
const stack = []
for (const line of txt.split('\n'))
if (line.length > 0)
stack.push(line.split(' ').map((s) => parseInt(s)))
for (let i = stack.length-1; i > 0; --i) {
const currRow = stack[i]
const prevRow = stack[i-1]
for (let j = 0; j < prevRow.length; ++j)
prevRow[j] += Math.max(currRow[j], currRow[j+1])
}
const result = stack[0][0]
alert(result + ', ' + (Date.now() - start) + 'ms')
})
由 bruce 于 2020-06-8 19:19 更新
