关于dp:leetcode-63DP-不同路径II

思路

走到点(i, j)，要么是从上边的点走过去的，要么是从右边的点走过去的

达到 (i,j) 的形式数 = 达到 (i-1,j) 的形式数 + 达到 (i,j-1) 的形式数：ways(i, j) = ways(i – 1, j) + ways(i, j – 1)ways(i,j)=ways(i−1,j)+ways(i,j−1)
能够用递归，也能够用自下而上的 DP：用数组去记录子问题的解（对应递归就是子调用）
dpi：达到 (i,j) 的门路数（形式数）。dpi = dpi – 1 + dpidpi=dpi−1+dpi
“阻碍”怎么解决
兴许你会想，遇到阻碍我要绕着走，但这种“动静”的想法不合乎 DP“状态”的思路
咱们思考单个点的“状态”：
阻碍点，是无奈到达的点，是达到形式数为 0 的点，是无奈从它这里走到别的点的点，即无奈提供给别的点形式数的点

base case

dp0=1dp0=1，出发点就是起点，什么都不必做，形式数 1
第一行其余的：以后点走不了，要么是它自身是“阻碍”，要么是它右边的点走不了，否则，门路数是 1，走一条直线过去
第一列其余的：以后点走不了，要么是它自身是“阻碍”，要么是它上边的点走不了，否则，门路数是 1，走一条竖线过去

代码

工夫复杂度 空间复杂度 都是 O(m*n)。有空会把降维的代码补充上来

const uniquePathsWithObstacles = (obstacleGrid) => {if (obstacleGrid[0][0] == 1) return 0; // 出发点就被阻碍堵住 
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
  // dp 数组初始化
  const dp = new Array(m);
  for (let i = 0; i < m; i++) dp[i] = new Array(n);
  // base case
  dp[0][0] = 1;                 // 起点就是出发点
  for (let i = 1; i < m; i++) { // 第一列其余的 case
    dp[i][0] = obstacleGrid[i][0] == 1 || dp[i - 1][0] == 0 ? 0 : 1;
  }
  for (let i = 1; i < n; i++) { // 第一行其余的 case
    dp[0][i] = obstacleGrid[0][i] == 1 || dp[0][i - 1] == 0 ? 0 : 1;
  }
  // 迭代
  for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {dp[i][j] = obstacleGrid[i][j] == 1 ?
        0 :
        dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1]; // 达到 (m-1,n-1) 的门路数
};

后记

当初写的题解有点啰嗦，慢慢来吧，同时也怕他人看不懂。我记得我刚看源码的时候，搜他人的文章看，本人难了解的中央没有提及，或一笔带过，小白的我只能无奈关掉。心想我本人写肯定要把本人说通，也要他人容易懂，不想让人带着纳闷点进来，又带着纳闷来到。随着我了解的深刻，我会精简表白并欠缺我的题解。

作者：xiao_ben_zhu
链接：https://leetcode-cn.com/probl…
起源：力扣（LeetCode）
著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。