63.不同路径 Ⅱ

题目：63.不同路径 Ⅱ

63.不同路径Ⅱ

题解：

一、 暴力搜索dfs

按照题目的思路，每次都让机器人往下或者往右走一个格。
如果走到障碍物上或走出边界，就说明这条路不对，就返回，如果最后走到了右下角，就让ans+1。

class Solution{
    int ans = 0;
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        dfs(obstacleGrid, 0, 0);
        return ans;
    }
    public void dfs(int[][] ob, int i, int j) {
        if (i >= ob.length || j >= ob[0].length)
            return;
        if (ob[i][j] == 1)
            return;
        if (i == ob.length - 1 && j == ob[0].length - 1)
            ans++;
        dfs(ob, i + 1, j);
        dfs(ob, i, j + 1);
    }
}

但是这种方法走了太多的重复路径，导致时间复杂度过高，最终无法accept，会超时。所以就引出了第二个方法，在暴力搜索的基础上加上记忆化数组，进行记忆化搜索，就可以减少重复路径了

二、记忆化搜索+dfs

在方法一的基础上加上一个记忆化数组dp，保存我们每次走过的路径数，如果遇到走过的路径就直接返回。

class Solution{
    int[][] dp;
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        dp = new int[m][n];
        return dfs_dp(obstacleGrid, 0, 0);

    }
    public int dfs_dp(int[][] ob, int i, int j) {
        if (i == ob.length || j == ob[0].length)
            return 0;
        if (ob[i][j] == 1)
            return 0;
        if (i == ob.length - 1 && j == ob[0].length - 1)
            return 1;
        if (dp[i][j] != 0)
            return dp[i][j];
        dp[i][j] += dfs_dp(ob, i + 1, j) + dfs_dp(ob, i, j + 1);
        return dp[i][j];
    }
}

三、动态规划

通过记忆化搜索，其实我们已经找到了动态转移方程.
动态转移方程：dp[i][j] = dp[i+1][j]+dp[i][j+1]
所以，我们根据动态转移方程和base case就可以写出动态规划形式的代码啦。

class Solution
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
      int m = obstacleGrid.length;
      int n = obstacleGrid[0].length;
      int[][] dp = new int[m+1][n+1];

      for (int i = m-1;i>=0;i--){
          for (int j = n-1;j>=0;j--){
              if (i==m-1&&j==n-1&&obstacleGrid[i][j]==0)
                  dp[i][j] = 1;
              else if (obstacleGrid[i][j]==0){
                  dp[i][j] = dp[i+1][j] + dp[i][j+1];
              }
          }
      }
      return dp[0][0];
  }

如果i，j超出数组范围的话就返回0，所以我让dp的大小是m+1×n+1，这样就不用判断越界的情况了，比较省事的写法。
萌新第二次更新题解，欢迎大佬在评论区提出改进，也欢迎大家多多交流！