63. Unique Paths II

Idea

這是 62. Unique Paths 的變化題
在一個只能向下向右走且有障礙物的網格中
我們要計算出所有可能路徑的數量

先不考慮空間複雜度，使用最直覺的 m * n 二維陣列去存 dp 的狀態
我們定義 dp[i][j] 為到達 obstacleGrid[i][j] 的所有可能路徑的數量

第一行和第一列的 dp 可以僅靠 obstacleGrid 算出

接下來的行列最佳解必須由 dp 的狀態逐一推論
可以觀察出以下規律:

1. obstacleGrid[i][j]若本身為障礙物，則不可能到達該點，因此 dp[i][j]必為 0。
2. 排除規律(1)，跟 Unique Paths 那題一樣，dp[i][j] 會是 dp[i - 1][j] 和 dp[i][j - 1]的加總，簡單的說就是下一個網格的狀態會取決於其左面和上面的狀態加總。

時間複雜度為 O( m * n )
空間複雜度為 O( m * n )

function uniquePathsWithObstacles(obstacleGrid) {
  if (obstacleGrid[0][0]) return 0
  const m = obstacleGrid.length,
    n = obstacleGrid[0].length,
    dp = Array.from(Array(m), (_) => Array(n).fill(0))
  dp[0][0] = 1
  for (let i = 1; i < m; i++) {
    if (obstacleGrid[i][0]) break
    dp[i][0] = 1
  }
  for (let i = 1; i < n; i++) {
    if (obstacleGrid[0][i]) break
    dp[0][i] = 1
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = obstacleGrid[i][j] ? 0 : dp[i - 1][j] + dp[i][j - 1]
    }
  }
  return dp[m - 1][n - 1]
}

Refactor

和同事讀書會的時候
想到了用記憶體 1 * n 的解法
只需要注意計算 dp 的順序和計算最左邊的 dp 時要防呆即可。

function uniquePathsWithObstacles(obstacleGrid) {
  if (obstacleGrid[0][0]) return 0
  const m = obstacleGrid.length,
    n = obstacleGrid[0].length,
    dp = Array(n).fill(0)
  for (let i = 0; i < n; i++) {
    if (obstacleGrid[0][i]) break
    dp[i] = 1
  }
  for (let i = 1; i < m; i++) {
    for (let j = 0; j < n; j++) {
      dp[j] = obstacleGrid[i][j] ? 0 : (dp[j - 1] || 0) + dp[j]
    }
  }
  return dp[n - 1]
}

tags: Leetcode JavaScript