Lettcode 每日一题： 63. 不同路径 II

解决方案

由题易知，机器人到达某个空白区域，其路径总数等于其上面块和左边块路径总和，那么可以得到一个递推公式：

f[ i ][ j ]= \begin{cases} 0,\quad & obstacleGrid[ i ][ j ] = 1\\ f[ i-1 ][ j ] + f[ i ][ j-1 ],\quad & obstacleGrid[ i ][ j ] = 0 \end{cases} \tag{1}

同时可以注意到，上式中 f[i][j] 只受它前面值的影响，那么意味着可以省去一个维度，利用数组滚动来实现

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function (obstacleGrid) {
  let m = obstacleGrid.length,
    n = obstacleGrid[0].length
  const dp = new Array(n).fill(0)
  dp[0] = 1
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (obstacleGrid[i][j]) {
        dp[j] = 0
      } else {
        j > 0 && (dp[j] += dp[j - 1]) // 这里dp[j]原本就是在它上面一行块的值，也就是 dp[i-1][j]的值，dp[j-1] 是原本 dp[i][j-1]的值
      }
    }
    console.log(dp)
  }
  return dp[n - 1]
}