62. 不同路径
image.png

  1. /**
  2.      * 1. 确定dp数组下标含义 dp[i][j] 到每一个坐标可能的路径种类
  3.      * 2. 递推公式 dp[i][j] = dp[i-1][j] dp[i][j-1]
  4.      * 3. 初始化 dp[i][0]=1 dp[0][i]=1 初始化横竖就可
  5.      * 4. 遍历顺序 一行一行遍历
  6.      * 5. 推导结果 。。。。。。。。
  7.      *
  8.      * @param m
  9.      * @param n
  10.      * @return
  11.      */
  12.     public static int uniquePaths(int m, int n) {
  13.         int[][] dp = new int[m][n];
  14.         //初始化
  15.         for (int i = 0; i < m; i++) {
  16.             dp[i][0] = 1;
  17.         }
  18.         for (int i = 0; i < n; i++) {
  19.             dp[0][i] = 1;
  20.         }
  22.         for (int i = 1; i < m; i++) {
  23.             for (int j = 1; j < n; j++) {
  24.                 dp[i][j] = dp[i-1][j]+dp[i][j-1];
  25.             } 
  26.         }
  27.         return dp[m-1][n-1];
  28.     }

63. 不同路径 II

image.png

  1. class Solution {
  2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3.         int n = obstacleGrid.length, m = obstacleGrid[0].length;
  4.         int[][] dp = new int[n][m];
  5.         //初始化
  6.         for (int i = 0; i < m; i++) {
  7.         if (obstacleGrid[0][i] == 1) break; //一旦遇到障碍，后续都到不了
  8.         dp[0][i] = 1;
  9.         }
  10.         for (int i = 0; i < n; i++) {
  11.         if (obstacleGrid[i][0] == 1) break; ////一旦遇到障碍，后续都到不了
  12.         dp[i][0] = 1;
  13.         }
  14.         for (int i = 1; i < n; i++) {
  15.             for (int j = 1; j < m; j++) {
  16.                 if (obstacleGrid[i][j] == 1) continue;
  17.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  18.             }
  19.         }
  20.         return dp[n - 1][m - 1];
  21.     }
  22. }