乐趣区

关于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)
著作权归作者所有。商业转载请分割作者取得受权,非商业转载请注明出处。

退出移动版