https://leetcode-cn.com/problems/unique-paths-ii/

Idea

这道题其实只要和第一道题大体是一样的思路
我们把障碍物对应的路径设置为0就好了 因为有障碍物就意味着该点无法达到
而在最上边和最左边的障碍物 我们必须把障碍物后面的路径也设置为0 因为无法到达

这里给出leetcode官方滚动数组优化的代码 因为滚动数组好像用的挺多 我来学习下这个思想

Code

  1. class Solution {
  2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3.         int n = obstacleGrid.length, m = obstacleGrid[0].length;
  4.         //n行m列
  5.         int[] f = new int[m]; //相当于1行
  7.         f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
  8.         for (int i = 0; i < n; ++i) {
  9.             for (int j = 0; j < m; ++j) {
  10.                 if (obstacleGrid[i][j] == 1) {
  11.                     f[j] = 0;
  12.                     continue;
  13.                 }
  14.                 if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
  15.                     f[j] += f[j - 1]; 
  16.                     /* i=0的时候 f[j]是是第一行第j+1个点的路径
  17.                     i==1的时候 f[1]+=f[0] 因为最左边都是1 f[0]始终相同 所以此时f[0]表示的是第二行的
  18.                     第0+1个点的路径
  19.                     */
  20.                     //所以 之所以能这样做 是因为最左边都是1 否则j=1的时候 f[1]+=obstacleGrid[0]
  21.                     //然后在进行循环增加 循环增加的原因是我们对于每一行只需要它上一行的值 它这一行的
  22.                     i-1的值 已经在这一行之中了
  23.                 }
  24.             }
  25.         }
  27.         return f[m - 1];
  28.     }
  29. }

感想

最近这些简单的DP一次就AC了 还是很爽的 感觉自己终于对dp有点感觉了
高中数学搞竞赛 考试150 的我 要是搞不定算法 哼 太可笑了