120. 三角形最小路径和

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如,给定三角形:
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

题解

状态转移方程:

dp(i)(j)+=min(dp(i-1)(j),dp(i-1)(j-1))

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(+triangle[i][j]) {
    let i = 1
    if (triangle.length == 1) {
        return triangle[0][0]
    }
    while (i < triangle.length) {
        let j = 0
        while (j < triangle[i].length) {
            if (j == 0) {
                triangle[i][j] += triangle[i - 1][j]
            } else if (j == triangle[i].length - 1) {
                triangle[i][j] += triangle[i - 1][triangle[i - 1].length - 1]
            } else {
                triangle[i][j] += Math.min(triangle[i - 1][j - 1], triangle[i - 1][j])
            }
            j++
        }
        i++
    }
    return Math.min(...triangle[triangle.length - 1])
};

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注