代码随想录算法训练营第三十四天 | 62.不同路径 | 63. 不同路径 II | 343.整数拆分 | 96.不同的二叉搜索树

Day 34 总结

• 自己实现中遇到哪些困难
  • 动态规划初始化逻辑：初始化哪些依赖并不存在的格子
  • 如何解决当前问题？
    • 通过分解成1个，2个或者多个子问题
    • 如何解决子问题？再继续分解，直到要解决一个根部问题，通过根部问题计算上一级子问题的答案，再去回答上上级子问题的答案。
  • 根部问题就是动态规划的初始化
  • 子问题的升级就是动态规划的推导公式
  • 发现解决问题嵌套着相同的子问题，想到使用动态规划
• 今日收获，记录一下自己的学习时间
  • 13:45 - 15:15

小总结

• 动态规划求路径：路径的依赖，障碍对初始化的影响
• 整数拆分：定义dp数组（拆分数字得到的最大值），dp数组的初始化
  • 说是拆两个数字，其实是已经保存了对第一个数字的更加细致的拆分的最好结果
• 不同二叉搜索树，一个数字对应着一个排列组合总数
  • 左树排列组合树*右树排列组合树=当前树的排列组合总数

62.不同路径

代码随想录

视频讲解：动态规划中如何初始化很重要！| LeetCode：62.不同路径_哔哩哔哩_bilibili

题目链接：62. 不同路径 - 力扣（LeetCode）

题目描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

实现思路：

每一个格子的可用路径由左边的格子和上边的格子可用路径总和得出。通过得到前面的所有格子的可用路径，计算出后面格子的可用路径。

dp数组：dp[i][j] 代表 i 行 j 列的格子的可用路径

推导公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]

初始化：初始化左上角的格子，只有一条路径可以到达该格子，dp[0][0] = 1。还需要初始化第一行和第一列，因为只能一个方向移动，所以都为1。（因为这个格子的依赖不存在，所以需要初始化）

遍历顺序：每个格子的依赖其上侧格子和左侧格子，所以按行或者按列遍历都可，我选择按行遍历，从1，1位置开始。

代码实现：

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

https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.htmlhttps://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html

视频讲解：动态规划，这次遇到障碍了| LeetCode：63. 不同路径 II_哔哩哔哩_bilibili

题目链接：63. 不同路径 II - 力扣（LeetCode）

题目描述：

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

实现思路：

与上一题【62.不同路径】不同的是会存在障碍物。那么障碍物的存在会影响到什么呢？就是你不能够从障碍物那一侧收集路径了。所以再收集路径的时候需要加一层判断。（可以不用加判断，直接把障碍物的格子路径设置为0）

dp数组：dp[i][j] 代表 i 行 j 列的格子的可用路径

推导公式：dp[i][j] = dp[i-1][j] + dp[i][j-1] （当本格子不是障碍物的时候）

初始化：第一行和第一列的依赖格子不存在，需要初始化他们。初始化规则与上题有小的差异，如果是障碍物，直接初始化为0，如果不是障碍物则继承上一个格子的路径数量（也就是初始化为1）。

遍历顺序：先行再列，从1，1开始。

代码实现：

class Solution {
    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 && obstacleGrid[i][0] != 1; i++) {
                dp[i][0] = 1;
        }        
        // 初始化第一行
        for (int j=0; j<n && obstacleGrid[0][j] != 1; j++) {
                dp[0][j] = 1;
        }
        for (int i=1; i<m; i++) {
            for (int j=1; j<n; j++) {
                if (obstacleGrid[i][j] != 1) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1] ;                    
                }
            }
        }

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

343.整数拆分 

代码随想录

视频讲解：动态规划，本题关键在于理解递推公式！| LeetCode：343. 整数拆分_哔哩哔哩_bilibili

题目链接：343. 整数拆分 - 力扣（LeetCode）

题目描述：

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

实现思路：

给一个正整数，拆成至少两个数相加，选择最大乘积。

简化一下，只拆成两个数，让这乘积最大化。那我肯定尝试一下从 1 * (n-1) 到 n/2 * n/2，比较哪个组成乘积最大。但这两个数又可以再继续拆成另外两个数，把这个数所能得到的乘积再次选择一个最大的。然后比较所有的组合的拆与不拆的最大值。

1 的话，不能再拆了，就是1。2 = 1+1 = 1，3 = 1 + 2 || 1 + 1 + 1 = 2， 4 = 1 +3 / 2 + 2 / 2 + 1 + 1 / 1 + 1 + 1 + 1 = 4。对于数字3来说，3本身要比把3拆开得到的价值更大。对于4来说，4本身和把4拆开得到的价值相等。5 = 1 + 4 / 2 + 3 =  6,  把5拆开可以得到比5更大的价值。1+1+1+1+1这种情况其实被隐含在了1+4和2+3中，因为4可以拆成4个1，2也可以拆成2个1，3也可以拆成3个1，但是当前这个数已经包含了所有拆分情况的最高价值，就无需再去单独讨论5个1的情况。其实就是把一个数拆成n个1，然后看这些1如何组合，来形成最大价值。然后记录每种组合的最大价值，再去匹配拆分。或者可以理解为，拆成两个数，再对第一个数进行更细致的拆分，dp数组保存了最优的拆分结果。

这里发现好像拆成3和4是最好的。因为其他数字本身价值都不如拆分价值高，如果能尽力分解成3，然后凑一些4，可能是最优的。8 = 4 + 4 = 3 + 3 + 1 + 1 = 2 + 3 + 3。

计算3除该数的值得到3个个数，然后通过余数判断组成3+0，3+1 还是 3+2.

dp数组：dp[i] 记录数字 i 的最优拆解法

推导公式：dp[i] = Max(dp[i] * k-i, i * (k-i ))【其中 i = 1~k-1】

初始化：dp[1] 的依赖不存在，初始化为1。

遍历顺序：从2开始，到目标数字n。

代码实现：

// 动态规划
class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        // 从数字2累计到数字n
        for (int i=2; i<=n; i++) {
            for (int j=1; j<i; j++) 
                // Math.max(dp[j] * (i-j), j * (i-j))，拆还是不拆哪个价值高
                // Math.max(dp[i]， xxx) 选择当前的最大值
                dp[i] = Math.max(dp[i], Math.max(dp[j] * (i-j), j * (i-j)));  
        }
        return dp[n];
    }
}

// 最优拆解
class Solution {
    public int integerBreak(int n) {
        if (n < 4) return n-1;

        int count = n / 3;
        int remainder = n % 3;
        // 只存在3
        if (remainder == 0) return (int)Math.pow(3, count);
        // 多了一个一，与一个3合并成4
        if (remainder == 1) return (int)Math.pow(3,count-1) * 4;
        // 多了两个1，合并成2
        return (int)Math.pow(3, count) * 2;
    }
}

96.不同的二叉搜索树 

代码随想录

视频讲解：代码随想录算法训练营第三十二天 

题目链接：96. 不同的二叉搜索树 - 力扣（LeetCode）

题目描述：

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

实现思路：

1个节点组成一个二叉搜索树，2个节点组成2个二叉搜索树，3个节点分以下情况，1.root节点左侧0个几点和右侧2个节点；2.root节点左侧一个节点 + 右侧一个节点；3.root节点左侧2节点，右侧0个节点。总计 (1*2) + (1*1) + (2*1)  = 5种方式。对于n个节点来说，左侧会出现 0~n-1个节点，对应的右侧会出现 n-1~0 个节点，将这些组合方式相乘，可以得到所有的分布情况。

dp数组：dp[i] 标识当 有 i 个节点的时候，所有的组合方式

推导公式：dp[i] = dp[j] * dp[k] （j=0~i-1，k=i-1~0）

初始化：0个节点这种情况是没有依赖的，初始化为1.

遍历顺序：前到后

代码实现：

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