代码随想录算法训练营打卡Day41 | LeetCode343 整数拆分、LeetCode96 不同的二叉搜索树

摘要

• 整数拆分和不同的二叉搜索树，这两个问题，都可以看做是从整体中不断拆出子结构（整数的子结构是更小的整数，二叉树的子结构是子树），模拟拆分子结构的过程，有助于思考递推公式。
• 这两题都是从dp数组的初始已知的部分开始，用子结构的dp数组去构造答案的。

LeetCode343 整数拆分

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

• 确定dp数组及数组下标的含义：

  • 对于一个正整数i，拆分为k个正整数，有很多种拆分方式，但应该有唯一的一种拆分方式使得拆分出的k个正整数的乘积最大。先尝试一维的dp数组，dp[i]为正整数i拆分为k个正整数的乘积的最大值。

• 确定递推公式，还是先看简单的子问题

  • 当n == 1时，1只有一种拆分方式，拆分成一个1,dp[1]显然是1。
  • 当n == 2时，2也只有一种拆分方式，拆分为两个1，所以dp[2]也是1。
  • 当n == 3时，3有两种拆分方式，一是先拆出一个1，得到[1, 2]，二是再把2拆分成一个1，得到[1, 1, 1]。可以把dp[3]的求解过程看成是这两种拆法的乘积的比较，即第一种是不把2继续往下拆，第二种是把2继续往下拆，写成表达式应该是dp[3]=max(1*(3-1), 1*dp[3-1])。
  • 当n == i时，假如我们先只拆出一个正整数j，得到[j, i-j]。对于[j, i-j]这一状态，要么j*(i-j)就是乘积的最大值，要么就还要继续拆分i-j来得到乘积的最大值，而dp[i-j]是拆分i-j为·k个正整数的乘积的最大值。假设我们已经知道了dp[i-j]的值，那么，对于拆出一个正整数j，dp[i]的值只可能是j*(i-j)和j*dp[i-j]中的较大值。
  • 对于n == i，如果我们遍历所有可能的j，就可以得到dp[i]真正的最大值。

  

• 根据递推公式，我们可以知道dp[0]、dp[1]、dp[2]的初始状态。

• 由于我们先知道的是较小的正整数的dp值，所以遍历方法应该是i逐渐增大到n，j也应该是从1逐渐增大到i。

题解代码如下

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

• 实际上，j只需要遍历到i / 2即可，因为当j > i / 2时，i - j就和之前j < i / 2的j的值重复了

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

LeetCode96 不同的二叉搜索树

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

• 确定dp数组及数组下标的含义：dp[i]是由i个节点组成，且节点值互不相同的二叉搜索树的种数。

• 确定递推公式，先看简单的子问题

  • 当n == 0，即没有节点时，树为空树，只有一种，dp[0]=1
  • 当n == 1时，树只有一个节点，所以也只有一种，dp[1]=1
  • 当n == 2时，树有两个节点，有两种情况：一是1作为根节点，二是2作为根节点，dp[2]=2
  • 当n == 3时，可以这样来考虑：
    1. 当1作为根节点时，左子树的节点数为0，右子树的节点数为2，有dp[0]*dp[2]种可能。
    2. 当2作为根节点时，左子树的节点数为1，右子树的节点数为1，有dp[1]*dp[1]种可能。
    3. 当3作为根节点时，左子树的节点数为2，右子树的节点数为0，有dp[2]*dp[0]种可能。
  • 当n == i时，设根节点的值为j，则左子树的节点数为j - 1，右子树的节点数为i - j。

  

• dp数组的初始值可以由递推公式得到

• 由于我们先知道的是i较小的dp[i]，所以i应该从小到大来构造dp数组

题解代码如下

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