代码随想录算法训练营第41天 | 343. 整数拆分、96.不同的二叉搜索树

343. 整数拆分 - 力扣（LeetCode）

思路:

• 使用动态规划

• 1. 确定dp数组以及下标的含义

     • dp[i]的定义为：拆分数字i能得到的最大乘积

  2. 确定递推公式

     • 状态转移方程为dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));

  3. dp数组如何初始化

     dp[2] = 1;
     // dp[0] 和 dp[1]无关紧要，不需要初始化
     // 实际意义上来说，0和1也不能被拆分

  4. 确定遍历顺序

     for(int i = 3; i <= n; ++i) {
         for(int j = 1; j <= i / 2; ++j) {
             dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
         }
     }

我的AC代码

动态规划

// 时间复杂度O(n^2),空间复杂度O(n)
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 0);
        dp[2] = 1;
        for(int i = 3; i <= n; ++i) {
            for(int j = 1; j <= i / 2; ++j) {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
};

标准答案

动态规划

// 时间复杂度O(n^2),空间复杂度O(n)
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};

贪心

// 时间复杂度：O(n) 空间复杂度：O(1)
// 本题也可以用贪心，采用数学结论
// 每次拆成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;
    }
};

96. 不同的二叉搜索树 - 力扣（LeetCode）

思路:

• 使用动态规划

• 1. 确定dp数组以及下标的含义

     • dp[i]的定义为：由1到i作为头结点的二叉搜索树的数量和，也可以理解为i个节点能构成的二叉搜索树总和

  2. 确定递推公式

     • 状态转移方程为

       for(int j = 1; j <= i; ++j) {
           dp[i] += dp[j - 1] * dp[i - j];
       }
       // 可以理解为由1到i轮流做头结点
       // i个节点能构成的二叉搜索树总和
       // 就是这i个节点轮流做头结点构成的二叉搜索树总和
       // 而每个节点做头结点时的数量
       // 则等于dp[左边子树节点个数]与dp[右子树节点个数]的乘积

  3. dp数组如何初始化

     dp[0] = 1
     // 0个节点也能勉强认为是一个二叉搜索树
     // 主要是为了后面乘起来不变成0

  4. 确定遍历顺序

     • 从前往后

我的AC代码

// 时间复杂度O(n ^ 2),空间复杂度O(n)
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[n];
    }
};

标准答案

// 时间复杂度O(n ^ 2),空间复杂度O(n)
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];
    }
};