题目

image.png

思路

  • 思路一：递归暴力破解，要求(m,n)的可能性，可以先求(m-1, n)和(m, n-1)的可能性之和，依次递归
  • 思路二：备忘录，由于递归重复了子问题，可以把重复的记录下来
  • 思路三：动态规划。我们知道（0,0）的可能性，一次就知道了(0,1)和(1,0）可能性，就是递归的逆过程

  • 思路四：优化dp数组的动态规划，优化数组画图就很快解决

    代码

    1. //1. 暴力递归，超时
    2.   public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    3.       return recur(obstacleGrid, obstacleGrid.length - 1, obstacleGrid[0].length - 1);
    4.   }
    6.   public int recur(int[][] obstacleGrid, int i, int j) {
    7.       if (i == 0 && j == 0 && obstacleGrid[i][j] == 0) return 1;
    8.       if (i < 0 || j < 0 || obstacleGrid[i][j] == 1) return 0;
    9.       return recur(obstacleGrid, i - 1, j) + recur(obstacleGrid, i, j - 1);
    10.   } 
    12.   //2.备忘录
    13.   Map<String, Integer> map = new HashMap<>();
    14.   public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    15.       return recur(obstacleGrid, obstacleGrid.length - 1, obstacleGrid[0].length - 1);
    16.   }
    18.   public int recur(int[][] obstacleGrid, int i, int j) {
    19.       String key = i + "-" + j;
    20.       if (map.containsKey(key)) return map.get(key);
    21.       if (i == 0 && j == 0 && obstacleGrid[i][j] == 0) return 1;
    22.       if (i < 0 || j < 0 || obstacleGrid[i][j] == 1) return 0;
    23.       int dist =  recur(obstacleGrid, i - 1, j) + recur(obstacleGrid, i, j - 1);
    24.       map.put(key, dist);
    25.       return dist;
    26.   } 
    28.   //3.动态规划
    29.   public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    30.      //dp[i][j]表示从00到ij的所有可能性
    31.      int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
    32.      if (obstacleGrid[0][0] == 1) return 0;
    33.      dp[0][0] = 1;
    34.      for (int i = 1; i < obstacleGrid.length; i++) {
    35.          if (obstacleGrid[i][0] == 1) {
    36.              dp[i][0] = 0;
    37.          } else {
    38.              dp[i][0] = dp[i - 1][0];
    39.          }
    40.      }
    41.      for (int j = 1; j < obstacleGrid[0].length; j++) {
    42.          if (obstacleGrid[0][j] == 1) {
    43.              dp[0][j] = 0;
    44.          } else {
    45.              dp[0][j] = dp[0][j - 1];
    46.          }
    47.      }
    48.      for (int i = 1; i < obstacleGrid.length; i++) {
    49.          for (int j = 1; j < obstacleGrid[0].length; j++) {
    50.              if (obstacleGrid[i][j] == 0) {
    51.                   dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    52.              } else {
    53.                  dp[i][j] = 0;
    54.              }
    55.          }
    56.      } 
    57.       return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    58.   }
    60.   //3.优化dp数组的动态规划，通过观察我们可以发现只用到了前一行和当前行的前一个，所以可以优化为一维数组
    61.   public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    62.      //dp[j] 表示从00到ij的所有可能性
    63.      int[] dp = new int[obstacleGrid[0].length];
    64.      if (obstacleGrid[0][0] == 1) return 0;
    65.      dp[0] = 1;
    66.      for (int j = 1; j < obstacleGrid[0].length; j++) {
    67.          if (obstacleGrid[0][j] == 1) {
    68.              dp[j] = 0;
    69.          } else {
    70.              dp[j] = dp[j - 1];
    71.          }
    72.      }
    73.      for (int i = 1; i < obstacleGrid.length; i++) {
    74.          //第一列是要更新的
    75.          dp[0] = obstacleGrid[i][0] == 1 ? 0 : dp[0];
    76.          for (int j = 1; j < obstacleGrid[0].length; j++) {
    77.              if (obstacleGrid[i][j] == 0) {
    78.                  dp[j] += dp[j - 1];
    79.              } else {
    80.                  dp[j] = 0;
    81.              }
    82.          }
    83.      } 
    84.       return dp[obstacleGrid[0].length - 1];
    85.   }

    不同路径II