动态规划3：三角形的最小路径和

从顶点出发，向下一层，只能走向左或向右的相邻的元素(比如第三层的6只能走到下一层的4和1)，问走到最底一层时，经过元素的最小和为多少。

        2
      3   4
    6   5    7
  4   1    8    3

记住： DP是从底到上回溯

定义状态f(m,n)为从底部一点出发，到达(m, n)点时的最小和, 则f(0,0)即为所求。

可得状态转移方程：

f(m, n) = min(f(m+1, n), f(m+1, n+1)) + arr[m][n]

arr为原始数据。

有初始值：最后一行(m === arr.length)时， f(m, j) = arr[m][j];

代码如下：

function result() {
    let arr = [
        [2],
        [3,4],
        [6,5,7],
        [4,1,8,3]
    ];


    const M = arr.length;
    // 初始化一个二维数组
    let res = [];
    for(let i = 0; i<M;i++) {
        res[i] = [];
    }

    // 初始值
    res[M-1] = arr[M-1];

    // DP
    for(let i = M-2; i>=0; i--) {
        for(let j = 0; j<=i; j++) {
            res[i][j] = Math.min(res[i+1][j], res[i+1][j+1]) + arr[i][j]
        }
    }

    return res[0][0];
}

时间复杂度为m x n, 空间复杂度也为m x n.

考虑下，还有哪儿能优化么？

上面计算每一层的res时，其实只跟下一层有关，所以我们可以将保存最小和结果的二维数组改为一维数组。

function result() {
    let arr = [
        [2],
        [3,4],
        [6,5,7],
        [4,1,8,3]
    ];

    const M = arr.length;
    let res = [...arr[M-1]];

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