[数据结构与算法]随想录一刷Day41——动态规划

Day41_动态规划

8. 整数拆分

343. 整数拆分

1. dp[i]表示数字i拆分后的最大乘积
2. 初始化条件，0和1拆分乘积最大为0，2拆分最大乘积为 1
3. dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)); ,选择当前拆分结果，拆分为两个数的乘积，i - j的拆分后的最大值与j的乘积，三个数中的最大值。
4. 由于每次递推都要用到前面的值，所以遍历顺序从前往后

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

贪心：数学方法求解
每次拆成n个3，如果剩下小于4，则保留，然后相乘

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

9. 不同的二叉搜索树

96. 不同的二叉搜索树

1. dp[i]表示以i为根节点的二叉搜索树的种类数
2. dp[i] += dp[j - 1] * dp[i - j];，每棵树可以由其左右子树的排布方式递推而来
3. 初始化 dp[0] = 1; 空树的排布方式只有一种
4. 从结点少的情况开始递推

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        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[n];
    }
};