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 }