【代码随想录】刷题Day41

1.整数拆分

1. 整数拆分

1.dp数组的含义：第i个就表示当前i能被拆分出相乘最大的整数

2.那么其实，所谓的后续的i对应的相乘最大整数其实就是前面的相乘最大整数拼凑而成，为了更好的区分我们将分离出来的数为j，那么我们的工作就是将一个又一个的j从i中剥离出，随后相乘即可。那么这种拼凑其实能分为两类：1.j和i-j相乘得到的数 2.j和dp[i-j]相乘得到的数。我们需要比较的条件其实就是找到最大值dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j));

3.初始化，0位置无意义，所以dp[0] = 0;1位置也无意义，所以dp[1] = 0;2位置只有一个拆分结果所以dp[2] = 1;

4.循环逻辑：第一层循环，我们需要对第i个位置进行操作，也就是说我们对i进行循环；第二层循环，我们需要考虑j由1开始到i结束，使得其不断拆分得到的max值中进行比较，那么循环就是j由1到i

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;
        for (int i = 3; i <= n; i++)
        {
            for (int j = 1; j < i; j++)
            {
                dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j));
            }
        }
        return dp[dp.size() - 1];
    }
};

我们知道，其实最大的数一定有的特征就是j都基本相近，那么其实我们需要考虑一半就行（j<i/2+1）。其目的就是能让所谓的n通过比较平均的拆分得到相近的数，这样使得数更大，一旦超过了一半说明其实该结果已经开始变小了，那么其实后面的循环都是无效的遍历，可以被剔除掉。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;
        for (int i = 3; i <= n; i++)
        {
            for (int j = 1; j < (i / 2 + 1); j++)
            {
                dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j));
            }
        }
        return dp[dp.size() - 1];
    }
};

2.不同的二叉搜索树

1. 不同的二叉搜索树

1.dp数组的含义：第i个就表示当前i能组成的不同的二叉搜索树个数

2.对于dp[i]位置，我们需要总结二叉搜索树的前后的关系。

首先dp[0]指的是一个空树，我们也将其视为一种情况；dp[1]为只有一个节点，我们视为一种情况；dp[2]有两个节点，随之的结果为2。

举例子针对dp[3]而言，其实所有结果有三种：一、节点为最小的，二、节点为第二小的，三、节点为最大的；对应三结果相加就是所谓的不同二叉搜索树的种类个数。

当节点最小：左边其实就是空节点为dp[0]的情况，右边有两个节点，对应两个节点的排列情况，其实就和dp[2]有两个节点，随之的结果为2的情况完全一致，只是数不一样，树的结构一模一样。那么对应的结果就是dp[0]*dp[2]

节点为第二小：左边一个节点，右边一个节点都是dp[1]的情况，最后的结果也就是对应的dp[1]*dp[1]

节点为最大的：右边为dp[0]的情况，左边有两个节点，对应两个节点的排列情况，其实就和dp[2]有两个节点，随之的结果为2的情况完全一致，结果就是dp[0]*dp[2]

3.那么我们发现了一个普遍的规律：对于dp[i]而言，其实最终的结果就是从0到n为头节点，看左右边的结果各位多少，随后相乘得到的数就是我们需要的。设定j是从0到n的，那么条件就是dp[i] += dp[j - 1] * dp[i - j];j不断变化，dp[i]也不断增加，最后的结果就是我们需要的。

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1,0);
        dp[0]=1;
        for(int i=1;i<=n;i++)
        {
            for (int j = 1; j <= i; j++) 
            {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[dp.size()-1];
    }
};