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

发布于 2023-01-08  312 次阅读


AI 摘要

本文介绍了 LeetCode 上的两道算法题目 343. 整数拆分 和 96. 不同的二叉搜索树,着重讲述了使用动态规划来解决这两道题的思路和方法,包括确定 dp 数组和下标的含义、递推公式、dp 数组的初始化和遍历顺序等,并给出了标准答案的代码和作者的 AC 代码。其中 343. 整数拆分 可以使用贪心算法来解决。这些算法思路和代码实现都有一定难度,需要有一定的算法基础才能理解和掌握。

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];
    }
};