三角形最小路径和

120. 三角形最小路径和

题目描述

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。我们用triangle 表示当前数组

i\k	k = 0	k = 1	k = 2	k = 3
i = 0	2
i = 1	3	4
i = 2	6	5	7
i = 3	4	1	8	3

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

思路

这道题用动态规划，我一开始的想法是用一位数组的动态规划，后来提交发现失败了， 一开始想的递推公式是 dp[i + 1] = d[i] + Math.min(triangle[i][j], triangle[i][j + 1])
后来发现是一个二维数组的动态规划

• 二维数组动态规划, 用dp 表示结果集
• 我们以 i 作为行, k 作为列， 注意题目的相邻节点
• 我们发现 当 k = 0 时, 那么他当前dp 值 应该是 dp[i][k] = dp[i-1][k] + triangle[i][k], dp[i][k] 因为 k = 0, 它只能从上往下走
• 我们看第三行即 i = 2时, 看 k = 1, dp[i][k] = triangle[i][k] + Math.min(dp[i - 1][k], dp[i - 1][k - 1]), 当 0 < k < column时
  我们dp[i][k] 应该 是用左上角的dp, 即dp[i - 1][k - 1]跟正上方的dp值，即dp[i - 1][k]取最小值 加上triangle[i][k]
• 同样是第三行即 i = 2时，看 k = 2, dp[i][k] = triangle[i][k] + dp[i - 1][k - 1], 此时 只能斜着走 即 2 -> 4 -> 这样走

dp 结果

i\k	k = 0	k = 1	k = 2	k = 3
i = 0	2
i = 1	5	6
i = 2	11	10（这里左上跟正上对比，取小的那个跟triangle相加）	13（这里只能斜着走，取6）
i = 3	15	11	18	16

最后取最后一行的最小那个即可

代码

var minimumTotal = function(triangle) {
    // dp[i + 1] = d[i] + Math.min(triangle[i][j], triangle[i][j + 1])
    let i = 0;
    let dp = []
    let row = triangle.length;
    while(i < row) {
        let column = triangle[i].length;  // 获取当前行的列数
        let dpColumn = []
        for(let k = 0; k < column; k++) {
            if(k == 0) {  // 列 = 0 时只能向下走，
                dpColumn.push(i == 0 ? triangle[i][k] : dp[i - 1][k] + triangle[i][k])
            } else if(k < column - 1) { // 列是中间列的话，就从正上方 或者左上方
                dpColumn.push(Math.min(dp[i - 1][k], dp[i - 1][k - 1]) + triangle[i][k]);
            } else {
                // 最后一列的时候只能够斜着走
                dpColumn.push(dp[i - 1][k - 1] + triangle[i][k])
            }
        }
        dp.push(dpColumn);
        i++;
    }
    return Math.min.call(null, ...dp[i - 1]);
};