思路
走到点(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）
著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。