120. 三角形最小路径和

题目: 给定一个三角形 triangle ，找出自顶向下的最小路径和

1. 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

2. 示例

   输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
   输出：11
   解释：如下面简图所示：
       2
       3 4
     6 5 7
     4 1 8 3
   自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

3. 示例

   输入：triangle = [[-10]]
   输出：-10

4. 提示

   • 1 <= triangle.length <= 200
   • triangle[0].length == 1
   • triangle[i].length == triangle[i - 1].length + 1
   • -104 <= triangle[i][j] <= 104

解法一：递归 + 空间优化

1. 使用对象来进行缓存

const has = {}
function dfs(x, y) {
  if (!triangle[x]) return 0
  if (!has[`${x},${y}`]) {
    has[`${x},${y}`] = Math.min(dfs(x + 1, y), dfs(x + 1, y + 1)) + triangle[x][y]
  }
  return has[`${x},${y}`]
}
return dfs(0, 0)

解法二：DP 分治

1. 覆盖降低空间使用

for (let i = triangle.length - 2; i >= 0; i--) {
  for (let j = 0; j < triangle[i].length; j++) {
    triangle[i][j] = Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]) + triangle[i][j]
  }
}
return triangle[0][0]

解法三：动态规划

1. 动态规划，自底向上

//克隆最后一行
let dp = [...triangle[triangle.length - 1]]
for (let i = triangle.length - 2; i >= 0; i--) {
  for (let j = 0; j <= i; j++) {
    dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j]
  }
}
return dp[0]

运行结果

TIP

如果有更好的解法，欢迎评论区讨论