[LC64] Minimum Path Sum

Friday, January 11, 2019

这道算法题属于经典的动态规划问题,来自 LeetCode #64:给定一个包含非负整数的 M x N 网格,请找出一条从左上角到右下角的路径(每次只能向下或者向右移动一步),使得路径上的数字总和为最小。

minimum path sum

状态定义

为了存储经过不同方向的路径之和,定义一个 $M \times N$ 的二维数组 $DP$,则 $DP[i][j]$ 表示从 $(0, 0)$ 走到 $(i, j)$ 的最小路径之和,其中 $0 \leqslant i < M, 0 \leqslant j < N$

状态方程

从第一个位置 $(0, 0)$ 考虑,可以有两种走法:向右走到 $(0, 1)$;向下走到 $(1, 0)$。它们的路径和分别为 $1 + 3 = 4$ 和 $1 + 1 = 2$。如果第二次从 $(0, 1)$ 走,同样有两种走法:向右走到 $(0, 2)$ 或者向下走到 $(1, 1)$。它们的路径和分别为 $4 + 1 = 5$ 和 $4 + 5 = 9$ …… 如此进行下去,可以得到下面这样的状态转移过程:

  • 走完第一行的路径之和为 $grid[0][0…j]$ 累加之和,其中 $0 \leqslant j < N$
  • 走完第一列的路径之和为 $grid[0…i][0]$ 累加之和,其中 $0 \leqslant i < M$
  • 除了第一行和第一列之外的其他位置 $grid[i][j]$ ($0<i<M,0<j<N$),必然都是从 $(0, 0)$ 出发经过目标点 $grid[i][j]$ 的上方 $(i-1, j)$ 或者左方 $(i, j-1)$ 到达的,那么我们需要找到这两个方向中路径之和的较小者,这样才能保证最终的路径之和最小
minimum path sum

综合上面的转移过程,可以得到以下的状态转移方程:

$$ DP[i][j] =\left\{ \begin{array}{lcl} grid[0][0] & & ({i = 0, j = 0})\\ \sum_{j=1}^{N-1}grid[i][j] & & ({i = 0, 1 \leqslant j < N})\\ \sum_{i=1}^{M-1}grid[i][j] & & ({1 \leqslant i < M, j = 0})\\ \min\{DP[i-1][j], DP[i][j-1]\} + grid[i][j] & & ({1 \leqslant i < M, 1 \leqslant j < N}) \end{array} \right. $$

代码实现

function minPathSum(grid) {
  if (!grid
      || grid.length === 0
      || grid[0] === null
      || grid[0].length === 0) {
    return 0
  }
  
  const rowsCount = grid.length
  const colsCount = grid[0].length
  
  const dp = makeArray(rowsCount, colsCount)
  
  // 初始状态即起始点的值
  dp[0][0] = grid[0][0]
  
  // 第一行
  for (let j = 1; j < colsCount; j++) {
    dp[0][j] = dp[0][j - 1] + grid[0][j]
  }
  
  // 第一列
  for (let i = 1; i < rowsCount; i++) {
    dp[i][0] = dp[i - 1][0] + grid[i][0]
  }
  
  // 其他位置
  for (let i = 1; i < rowsCount; i++) {
    for (let j = 1; j < colsCount; j++) {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
    }
  }
  
  return dp[rowsCount - 1][colsCount - 1]
}

function makeArray(rowsCount, colsCount) {
  const rows = (new Array(rowsCount))
  return colsCount ? rows.fill().map(() => new Array(colsCount)) : rows
}

复杂度分析

对于 M x N 网格,

  • 时间复杂度:由于每个位置都会计算一次,且只比较来自左方的最小路径之和与来自上方的最小路径之和,所以时间复杂度为 $O(M \times N)$
  • 空间复杂度:由于数组 $DP$ 存储了每个位置的最小路径之和,所以空间复杂度为 $O(M \times N)$