JLUVicent

96不同的二叉搜索树&343整数拆分

 
  • 2023年 03月27日
  • 0 阅读

day41

343.整数拆分

题目链接：343. 整数拆分

解题思路：参考 视频

拆分的原则是尽可能拆分成相同的数，这样最终的结果才能保持最大，这在之后的代码优化里面有体现，具体为j <= i/2

动态规划

动态规划五部曲：

1.dp数组及下标的含义：对i进行拆分得到的最大的乘积值为dp[i]

2.递推公式：$j * (i - j)$针对两个数的乘积，$j * dp[i - j]$针对三个及以上的数的乘积，最终所有的结果取最大值

dp[i] = max(j * dp[i-j], dp[i]);	//还需要和dp[i]本身取最大值
dp[i] = max( j * (i - j ), dp[i]);

这里注意拆分$j$和拆分$i-j$是一样的情况。

3.递推公式初始化

dp[0] = 0;	//无意义
dp[1] = 0;	//无意义
dp[2] = 1;	//初始化为1

4.遍历顺序：从前向后，从i = 3开始

5.打印dp数组，用来调bug

343.整数拆分

注意一个细节：dp下标从0开始最后到n，所以在dp初始化的时候需要初始化大小为$n+1$

class Solution {
public:
    // 时间：O(n^2)
    // 空间：O(n)
    int integerBreak(int n) {
        vector<int> dp(n+1,0);    //定义dp数组
        dp[0] = 0;	//这个无意义，可以不写
        dp[1] = 0;  //这个无意义，可以不写
        dp[2] = 1;
        for( int i = 3; i <= n; i++){
            for( int j = 1; j <= i/2; j++){
                dp[i] = max(j * dp[i-j], dp[i]);
                dp[i] = max( j * (i - j ), dp[i]);
            }
        }
        return dp[n];
    }
};

贪心

思路：每次拆分成n个3，如果剩下的是4，则保留4，然后相乘。这个是思路，具体原因需要数学证明。

class Solution {
public:
    int integerBreak(int n) {
        int result = 1;
        if( n == 1 ) return 0;
        if( n == 2 ) return 1;
        if( n == 3 ) return 2;
        while( n > 4 ){
            result *= 3;
            n -= 3;
        }
        result *= n;
        return result;
    }
};

96.不同的二叉搜索树

题目链接：96. 不同的二叉搜索树

解题思路：参考 视频

image-20230327102119451

1.确定dp数组以及下标i的含义：dp[i]种不同的二叉搜索树

2.确定递推公式

dp[i] += dp[j - 1] * dp[i - j];

上面$dp[j-1]$统计的是第j个二叉树的左子树的数量，$dp[i-j]$统计的是第j个二叉树的右子树的数量

3.初始化：$dp[0] = 1;$ 空二叉树也可以是二叉搜索树

4.遍历顺序：从前向后遍历，初始是从1开始的

for( int i = 1; i <= n; i++){
    for( int j = 1; j <= i; j++){
    }
}

5.打印数组

96.不同的二叉搜索树2

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1,0);
        dp[0] = 1;  // dp数组初始化
        for( int i = 1; i <= n; i++){
            for( int j = 1; j <= i ; j++){
                dp[i] += dp[j -1] * dp[i - j];  //第一个为左子树的个数，第二个为右子树的个数
            }
        }
        return dp[n];
    }
};
搜索