代码随想录Day34 LeetCode T343整数拆分 T96 不同的二叉搜索树

前言

让我们回归思考一下贪心算法的动规五部曲

第一步:确定递归数组含义(分析好含义才能解决的更透彻)

第二步:确定dp数组的递推公式(其实很多情况下有了递推公式才知道怎么初始化值)

第三步:初始化dp数组(其实也是为接下来的递推做准备)

第四步:确定遍历顺序(很多情况下是对遍历顺序有要求的)

第五步:打印dp数组(如果遇到错误可以打印一下dp数组看看和我们推理的dp数组有啥不同,错在哪里了,更好的解决问题)

LeetCode T343 整数拆分

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

题目思路:

这里我们知道一个大于等于2的数字可以拆分,我们可以想到首先它可以拆成两个数字,这里我们固定第一个数字,让第二个数字继续拆分

我们用3和4举例

第一步:确定递归数组含义

dp[i]就表示目前i这个数字可以拆分成的最大值

第二步:确定dp数组的递推公式(其实很多情况下有了递推公式才知道怎么初始化值)

我们发现递推公式其实就是求横向和竖向的最大值,公式如下

dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]))

第三步:初始化dp数组(其实也是为接下来的递推做准备)

首先dp[0]和dp[1]是没有意义的,因为0和1无法分解

dp[2] = 1,因为2可以分为1和1,是最小的两个数

dp一定要初始化为n+1大小的

第四步:确定遍历顺序(很多情况下是对遍历顺序有要求的)

这里因为想知道dp[i]就得知道前面的dp[i-1]等,所以一定是从前往后遍历

注意这里有个小优化,因为我们知道一定是几个相同或接近的值是最大的,比如10里面两个数字相乘一定是5*5最大,所以我们j直接取得i/2即可

第五步:打印dp数组(如果遇到错误可以打印一下dp数组看看和我们推理的dp数组有啥不同,错在哪里了,更好的解决问题)

题目代码:

class Solution {
    public int integerBreak(int n) {
        //dp数组的含义,拆解n得到的最大乘积
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i = 3;i<=n;i++){
            for(int j = 1;j<=i/2;j++){
                dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
}

LeetCode T96 不同的二叉搜索树

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

题目思路:

这题我们发现n取3的时候,这个二叉树的左子树的形态和右子树的形态和n取2的时候是一样的,这时候我们就想到了动规

第一步:确定递归数组含义(分析好含义才能解决的更透彻)

dp[i]表示n取i时,这种不同二叉搜索树的个数

第二步:确定dp数组的递推公式(其实很多情况下有了递推公式才知道怎么初始化值)

dp[i]的值就是左子树可能的方法数*右子树可能的方法数的累加

为什么是乘法而不是加法呢?

举例:加入n取10,左子树有6种不同的取法,右子树有10种,这里肯定是左子树任取一种来对应右子树任取一种的方法(以上的6和10是瞎编的,仅供举例说明)

第三步:初始化dp数组(其实也是为接下来的递推做准备)

dp[0] = 1;
//0个节点,既是完全二叉树,又是满二叉树,同样也是二叉搜索树
dp[1] = 1;

第四步:确定遍历顺序(很多情况下是对遍历顺序有要求的)

同样是从前向后遍历,因为后面的元素依赖前面的元素产生

第五步:打印dp数组(如果遇到错误可以打印一下dp数组看看和我们推理的dp数组有啥不同,错在哪里了,更好的解决问题)

题目代码:

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