算法 D40 | 动态编程 3 | 343. 整数分割 96. 不同的二进制搜索树

今天两题都挺有难度，建议大家思考一下没思路，直接看题解，第一次做，硬想很难想出来。

343. 整数拆分 

代码随想录

视频讲解：动态规划，本题关键在于理解递推公式！| LeetCode：343. 整数拆分_哔哩哔哩_bilibili

Python:

关键是想清楚递推关系dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))。

在取最大值的时候，为什么还要比较dp[i]呢？

- 因为在递推公式推导的过程中，每次计算dp[i]，取最大的而已。（同个i下，不同的j更新取最大的dp[i]）

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0]*(n+1)
        dp[2] = 1
        for i in range(3, n+1):
            for j in range(1, i):
                dp[i] = max(dp[i], max((i-j)*j, dp[i-j]*j))
        return dp[n]

C++:

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

96.不同的二叉搜索树 

代码随想录

视屏讲解：动态规划找到子状态之间的关系很重要！| LeetCode：96.不同的二叉搜索树_哔哩哔哩_bilibili

Python:

重点是发现递推关系，i的左子树的形状（left个）和left的dp的形状（布局）一致。

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[0] = 1
        for i in range(1, n+1):
            for j in range(1, i+1):
                dp[i] += dp[j-1] * dp[i-j]
        return dp[n]

C++:

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