64.最小路径和.md

64.最小路径和

/*
 * @lc app=leetcode.cn id=64 lang=typescript
 *
 * [64] 最小路径和
 */

// @lc code=start
function minPathSum(grid: number[][]): number {}
// @lc code=end

解法 1: 动态规划

1. 子问题: 从左上角到当前位置的最小路径
2. 状态: dp[i][j] 表示从 0,0 到 i,j 的最小路径和
3. DP 方程:
   • dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i][j]
   • 简化 dp[j]=min(dp[j-1],dp[j])+grid[i][j]
4. 初始状态:
   • dp[0]=[0,Infinity,Infinity,...]

function minPathSum(grid: number[][]): number {
  const dp: number[] = [0]

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      dp[j] = Math.min(dp[j] ?? Infinity, dp[j - 1] ?? Infinity) + grid[i][j]
    }
  }
  return dp[dp.length - 1]
}

Case

test.each([
  {
    input: {
      grid: [
        [1, 3, 1],
        [1, 5, 1],
        [4, 2, 1],
      ],
    },
    output: 7,
  },
  {
    input: {
      grid: [
        [1, 2, 3],
        [4, 5, 6],
      ],
    },
    output: 12,
  },
  {
    input: {
      grid: [
        [1, 2],
        [1, 1],
      ],
    },
    output: 3,
  },
])(`input: grid = $input.grid`, ({ input: { grid }, output }) => {
  expect(minPathSum(grid)).toBe(output)
})