343. 整数拆分

• dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
• 递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)); 要么拆两个直接乘，要么拆两个及以上。
• 初始化：dp[2] = 1,注意拆0和1没意义。
• 遍历顺序，从前往后，先得到小的dp再算大的dp。
• 动态规划里经常考虑实际意义数组下标从1开始才有意义，最后求的也是dp[m],所以数组大小要多开一位。

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; j++) {
                dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j));
            }
        }
        return dp[n];
    }
};

96.不同的二叉搜索树

一刷过。