931. 下降路径最小和

题号：931
来源：LeetCode
难度：中等
标签：dp 矩阵
语言：TypeScript
解法：1 个
作者：lmliheng
最近更新：2026-09-27

TypeScript · O(n*m) 时间 · O(n*m) 空间 · 更新于 2026-09-27

dp 取上一行相邻三格最小值累加，未取末行最小

typescript

/**
 * @difficulty medium
 * @tags dp,矩阵
 * @time O(n*m)
 * @space O(n*m)
 * @note dp 取上一行相邻三格最小值累加，未取末行最小
 * @931. 下降路径最小和
 */

let matrix: number[][] = [[2,1,3],[6,5,4],[7,8,9]]
let m: number = matrix.length
let n: number = matrix[0].length
let dp: number[][] = new Array(m).fill(0).map(() => new Array(n).fill(0))
for (let i = 0; i < n; i++) {
    dp[0][i] = matrix[0][i]
}
for (let i = 1; i < m; i++) {
    for (let j = 0; j < n; j++) {
        if (j === 0) {
            dp[i][0] = Math.min(dp[i - 1][0], dp[i - 1][1]) + matrix[i][0]
            console.log("1:",dp[i][0])
        } else if (j === n - 1) {
            dp[i][n - 1] = Math.min(dp[i - 1][n - 1], dp[i - 1][n - 2]) + matrix[i][n - 1]
        } else {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1], dp[i - 1][j + 1]) + matrix[i][j]
        }
    }
}
let lastRow: number[] = dp[m - 1]
let a = 1

export {};

源码：ts/leetcode/931. 下降路径最小和.ts

在 GitHub 上查看题目所在目录：lmliheng/algorithm

931. 下降路径最小和 ​

931. 下降路径最小和