2023年10月18日 - 动态规划3

343. 整数拆分

i拆成两个 j * (i - j)

i拆成三个及以上 j * dp[i - j]，因为dp[i - j]是一个最大的值，不一定是拆成几部分

 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. 不同的二叉搜索树

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