day39

1、leetcode62 不同路径

1. 步骤

   1. 确定dp数组（dp table）以及下标的含义
      • dp[i] [j] : 从(0,0)到(i,j)的路径数量
   2. 确定递推公式
      • (i,j) 可由 (i-1,j)、(i,j-1)到达【已知：每次只能向下或者向右移动一步】
      • dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]
   3. dp数组如何初始化
      • 已知：每次只能向下或者向右移动一步
        • dp[i] [0] = 1
        • dp[0] [j] = 1
   4. 确定遍历顺序
      • 一层一层，从前向后遍历
   5. 举例推导dp数组

2. 代码

   class Solution {
       public int uniquePaths(int m, int n) {
           int[][] dp = new int[m][n];
   
           for (int i = 0; i < m; i++) dp[i][0] = 1;
           for (int j = 0; j < n; j++) dp[0][j] = 1;
   
           for(int i=1; i<m; i++) {
               for(int j=1; j<n; j++) {
                   dp[i][j] = dp[i-1][j] + dp[i][j-1];
               }
           }
   
           return dp[m-1][n-1];
       }
   }
   

2、leetcode63 不同路径Ⅱ

1. 步骤

   1. 确定dp数组（dp table）以及下标的含义

      • dp[i] [j] : 从(0,0)到(i,j)的路径数量

   2. 确定递推公式

      • (i,j) 可由 (i-1,j)、(i,j-1)到达【已知：每次只能向下或者向右移动一步】【前提是（i,j）可达】

      • if(obstacleGrid[i][j] == 0){
        	dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]
        }
        

   3. dp数组如何初始化

      • 已知：每次只能向下或者向右移动一步 【且该点可达】

        • for(int i=0; i<row && obstacleGrid[i][0] == 0; i++){
          	dp[i][0] = 1;
          }
          for(int j=0; i<col && obstacleGrid[0][j] == 0; j++){
          	dp[0][j] = 1;
          }
          

   4. 确定遍历顺序

      • 一层一层，从前向后遍历

   5. 举例推导dp数组

2. 代码

   class Solution {
       public int uniquePathsWithObstacles(int[][] obstacleGrid) {
           int row = obstacleGrid.length;
           int col = obstacleGrid[0].length;
   
           int[][] dp = new int[row][col];
   
           if (obstacleGrid[row - 1][col - 1] == 1 || obstacleGrid[0][0] == 1) {
                return 0;
           }
   
           for(int i=0; i<row && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1; 
           for(int j=0; j<col && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
   
           for(int i=1; i<row; i++) {
               for(int j=1; j<col; j++) {
                   if(obstacleGrid[i][j] == 1) {
                       continue;
                   }
                   dp[i][j] = dp[i-1][j] + dp[i][j-1];
               }
           }
   
           return dp[row-1][col-1];
       }
   }