代码随想录算法训练营第三十九天 | 动态规划part02

题目：

62.不同路径
63. 不同路径 II

学习内容：

62.不同路径

动态规划五部曲：

1. dp数组的含义：dp[i][j]表示从(0, 0)出发，到达(i, j)有dp[i][j]不同路径；
2. 确定递归公式：由于机器人每次只能向下或者向右移动一步，所以dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
3. dp数组的初始化，由于是二维数组，我们需要对第一列和第一行初始化，全部初始化为1；
4. 确定遍历顺序：从上到下，从左到右；
5. 举例推导dp数组

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 0; i < m; i++) {
            dp[i][0] = 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];
    }
}

63. 不同路径 II

这道题和上一题最不同的就是有障碍，还是动态规划五部曲：

1. 确定dp数组含义：dp[i][j]表示从(0, 0)到(i, j)的路径数量；
2. 确定递归公式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
3. dp数组的初始化：这里就要注意了，因为障碍物的原因，如果第一行/列有障碍物，就停止dp数组的初始化，因为路径被堵死了！
4. 确定遍历顺序：从上到下，从左到右，这里遍历也要注意，如果出现障碍物，也是要跳出当前循环的。
5. 举例推导dp数组

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 确定dp数组
        int m = obstacleGrid.length; // 确定行数
        int n = obstacleGrid[0].length; // 确定列数
        int[][] dp = new int[m][n];

        // dp数组的初始化，第一行/列
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1) break;
            dp[0][i] = 1;
        }
        for (int j = 0; j < m; j++) {
            if (obstacleGrid[j][0] == 1) break;
            dp[j][0] = 1;
        }
        // 确定遍历条件和递归公式
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

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

学习时间：

2024.4.24