day39 动态规划

•  62.不同路径 

  • * 机器人每次只可以向右 或者 向下 (每次向右走 )
    * dp[i][0] = 1;
    * dp[0][j] = 1;
    *
    * dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    *
    * i的范围 [0,m - 1]
    * j的范围 [0,n - 1]

•  63. 不同路径 II 
  • 解法同上，需要考虑障碍物​​​​​​​
    • 初始化的时候 当发现边界出现障碍物，之后的数据也不能置1
    • dp生成值时，当无障碍物时，才生成

package algor.trainingcamp;

/**
 * @author lizhe
 * @version 1.0
 * @description:
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * 问总共有多少条不同的路径？
 *
 * 机器人每次只可以向右 或者 向下 (每次向右走 )
 * dp[i][0] = 1;
 * dp[0][j] = 1;
 *
 * dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
 *
 * i的范围 [0,m - 1]
 * j的范围 [0,n - 1]
 * @date 2023/5/13 19:17
 */
public class LeetCode62 {
    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 i = 0;i < n;i++){
            dp[0][i] = 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];
    }
}

package algor.trainingcamp;

/**
 * @author lizhe
 * @version 1.0
 * @description: 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
 * 网格中的障碍物和空位置分别用 1 和 0 来表示。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
 * <p>
 * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
 * @date 2023/5/13 19:29
 * <p>
 * 解法和62相同，多了障碍处理
 * 1. 初始化边界
 * 从(0, 0)的位置到(i, 0)的路径只有一条，所以dp[i][0]一定为1，dp[0][j]也同理。
 * 但如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0。
 *
 * 2. dp 数组生成时候 只考虑无障碍情况
 * 3. 当d
 */
public class LeetCode63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {
            if(obstacleGrid[i][0] == 1){
                break;
            }else{
                dp[i][0] = 1;
            }

        }

        for (int i = 0; i < n; i++) {
            if(obstacleGrid[0][i] == 1){
                break;
            }else{
                dp[0][i] = 1;
            }
        }

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

        return dp[m - 1][n - 1];
    }
}