第九章 动态规划part02

62.不同路径

本题大家掌握动态规划的方法就可以。 数论方法 有点非主流，很难想到。
文章讲解

思路

1. 确定dp数组（dp table）以及下标的含义
   dp[i][j]代表从（0，0）出发，到（i, j）有dp[i][j]种走法
2. 确定递推公式
   到d[i][j]只能从d[i-1][j]和d[i][j-1]两个方向
   回顾：d[i-1][j]表示从 (i-1, j) 有几条路径，d[i][j-1]同理
   所以 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
3. dp数组的初始化
   因为从(0, 0)的位置到(i, 0)的路径只有一条，所以dp[i][0]=0，dp[j][0]同理

for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

4. 确定遍历顺序：从左到右
5. 举例推导dp数组

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 循环从 i = 1 和 j = 1 开始，因为第0行和第0列已经在初始化阶段设置好了
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1]; //计算从网格的左上角（0, 0）到右下角（m-1, n-1）有多少条不同的路径，所以不是直接返回dp[m][n]
    }

使用一维数组的解法

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        
        // 初始化 dp 数组为 1
        //dp[i] 表示在某一行，从起点到第 i 列的路径数量。因为在第一行，每个位置的路径数量都是 1（只能一直向右移动）。
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        
        // 迭代计算路径数量
       //外层循环：从第二行开始遍历（j = 1），直到最后一行（j < m）。内层循环：从第二列开始遍历（i = 1），直到最后一列（i < n）。
        for (int j = 1; j < m; j++) {
            for (int i = 1; i < n; i++) {
                dp[i] += dp[i - 1];  //当前位置 dp[i] 的路径数量等于上一个位置 dp[i] 的路径数量加上左边位置 dp[i - 1] 的路径数量。
            }
        }
        
        return dp[n - 1];
    }

63. 不同路径 II

文章讲解

思路

• 有障碍物实际上就是标记对应的dp table（dp数组）保持初始值(0)就可以了。每个位置 dp[i][j] 表示从起点 (0, 0) 到该位置的所有不同路径的数量。如果当前位置 (i, j) 有障碍物，则不能通过该位置。因此，dp[i][j] 应该为0，表示从起点到 (i, j) 的路径数为0。
• 动规五部曲

1. 确定dp数组（dp table）以及下标的含义
   dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。

2. 确定递推公式
   递推公式和62.不同路径一样，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
   但这里需要注意一点，因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。
   所以代码为：

if (obstacleGrid[i][j] == 0) { // 当(i, j)没有障碍的时候，再推导dp[i][j]
    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}

3. dp数组如何初始化
   和62.不同路径类似，只是要考虑障碍物的情况

for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

注意代码里for循环的终止条件，一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，dp[0][j]同理

4. 确定遍历顺序：从左到右
5. 举例推导dp数组

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        //如果起点或终点有障碍物，直接返回0
        if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) return 0;
        // 初始化第一列：如果某位置有障碍物，后续所有位置路径数都为0
        for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++){
            dp[i][0] = 1; 
        }
        // 初始化第一行
        for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++){
            dp[0][j] = 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];
                }else{
                    dp[i][j] = 0;
                }
            }
        }
        return dp[m-1][n-1];
    }
}

343. 整数拆分 （可跳过）

本题思路并不容易想，一刷建议可以跳过。如果学有余力，可以看视频理解一波。
文章讲解

思路

• 拆成m个数，数值近似相等，乘积才会尽可能大。比如，10拆成4和6，4可以拆分成2和2；6可以拆分成2和4；所以拆分10的数字的乘积依赖于之前较小数的拆分。

1. 确定dp数组（dp table）以及下标的含义
   dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
2. 确定递推公式
    （1）拆成两个数的情况：j(i-j)
    （2）拆成三个数及以上：jdp(i-j）
             所以递推公式为 dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
    （3）dp的初始化
             dp[0] dp[1] 就不应该初始化，也就是没有意义的数值。所以只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1
    （4）确定遍历顺序：从前向后
    （5）举例推导dp数组

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n+1]; //数组大小是n+1，因为索引是从0开始的
        dp[2] = 1;
        for(int i = 3; i <= n; i++){
            for(int j = 1; j <= i-j; j++){
                // 这里的 j 其实最大值为 i-j,再大只不过是重复而已，
                //并且，在本题中，我们分析 dp[0], dp[1]都是无意义的，
                //j 最大到 i-j,就不会用到 dp[0]与dp[1]
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
                // dp[i] 是我们当前已知的，将 i 拆分后的最大乘积。
                // Math.max(j * (i - j), j * dp[i - j]) 是我们尝试用当前的 j 和 i - j 来更新 dp[i] 的值。
            }
        }
        return dp[n];
    }
}

96. .不同的二叉搜索树 （可跳过）

本题思路并不容易想，一刷建议可以跳过。 如果学有余力，可以看视频理解一波。
文章讲解

之后再来写，今天的智商已经用完了