64. 最小路径和

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

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

转移取上/左较小值再加当前格

/**
 * @difficulty medium
 * @tags dp,矩阵
 * @time O(m*n)
 * @space O(m*n)
 * @note 转移取上/左较小值再加当前格
 * @64. 最小路径和
 */

let grid: number[][] = [[1,3,1],[1,5,1],[4,2,1]]
// dp
let m: number = grid.length
let n: number = grid[0].length
let dp: number[][] = new Array(m).fill(0).map(() => new Array(n).fill(0))
dp[0][0] = grid[0][0]
for (let i = 1; i < m; i++) {
    dp[i][0] = grid[i][0] + dp[i-1][0]
}
for (let i = 1; i < n; i++) {
    dp[0][i] = grid[0][i] + dp[0][i-1]
}
for (let x = 1; x < m; x++) {
    for (let y = 1; y < n; y++) {
        dp[x][y] = Math.min(dp[x-1][y], dp[x][y-1]) + grid[x][y]
    }
}
console.log(dp[m-1][n-1])

export {};

源码：ts/leetcode/64. 最小路径和.ts

---

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