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

 343. 整数拆分

要求：

将一个正数拆分成N个正整数，使得这N个正整数的乘机是最大的

思路：

DP数组：dp[n] N 的时候，它的乘机最大值

注意：

不是i*dp[n-i]就是最大值，因为如果用dp就证明要开始拆分了，如果我不拆分，就是用的这两个数的话，那么就是单纯的 i* (n-i)

代码：

 1 // 要求：将N 拆分成 K个正整数的和（K》=2） 并让这些整数的乘机最大化
 2 // 
 3 // 可能的思路：数在这个范围内，同时相差最小
 4 // 难点：如何求的乘机最大化
 5 // 
 6 // 动态规划的思路：
 7 //    dp的定义：dp[n] N个数它的乘机最大化
 8 // 递推公式分为两种：
 9 //    1，两个数之间取最大值 ： i *(n-i)
10 //    2，三个及以上去的最大值 : i * dp[n-i]
11 //
12 int integerBreak(int n) {
13     vector<int> dp(n+1, 0);
14     if (n < 2) return dp[n];
15 
16     dp[2] = 1;
17     for (int i = 3; i < dp.size(); i++)
18     {
19         
20         for (int j = 0; j <= i; j++)
21         {
22             //两个值的情况
23             int cur1 = j * (i - j);
24             int cur2 = j * dp[i - j];
25 
26             dp[i] = max(dp[i], max(cur1, cur2));
27         }
28     }
29 
30     return dp[n];
31 }