一壮吩、原題
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
Note: You may assume that n is not less than 2 and not larger than 58.
二苍蔬、題意
給定一個大于1的正整數(shù)咨察，求如何將這個數(shù)拆成幾個正整數(shù)的和（至少要拆成兩個）匹涮，使得這幾個正整數(shù)的乘積最大鸟辅。
三倍奢、思路
動態(tài)規(guī)劃思想：定義狀態(tài)熟嫩、求出狀態(tài)轉(zhuǎn)移方程
定義狀態(tài)：從簡單情況開始考慮：
- 整數(shù)2：2 = 1 + 1宅此，則最大乘積為1机错；
- 整數(shù)3：3 = 2 + 1，則最大乘積為2父腕；
- 整數(shù)4：4 = 3 + 1 = 2 + 2弱匪，則最大乘積為4。先考慮3 + 1璧亮，和為3的最大乘積為2（由上面推出的結(jié)果）萧诫，比3還小斥难，所以肯定選擇3，所以選擇3 + 1的最大乘積為3 × 1 = 3帘饶；考慮2 + 2哑诊，和為2的最大成績?yōu)?，比2還小及刻，所以選擇2 + 2的最大乘積為2 × 2 = 4搭儒，比較這兩種情況結(jié)果為4；
- 整數(shù)5：5 = 4 + 1 = 3 + 2提茁，則最大乘積為6淹禾。同4一樣推斷。
- 整數(shù)6：6 = 5 + 1 = 4 + 2 = 3 + 3茴扁，最大乘積為9铃岔。考慮這三種情況峭火，選擇5 + 1的最大乘積為6毁习，選擇4 + 2的最大乘積為8，選擇3 + 3的最大乘積為9卖丸，比較這三種情況纺且，結(jié)果為9；
......
綜上稍浆，對于一個正整數(shù)n载碌，則n的組合情況有 n = (n - 1) + 1 = (n - 2) + 2 = ... ，對于其中一種情況(n - i)與i衅枫，可以如果(n - i)大于和為(n - i)的最大乘積（例如3嫁艇，和為3的最大乘積為2，而3本身大于2弦撩，則選擇3步咪，不選擇其最大乘積)，則選擇(n - i)本身益楼，不選擇和為(n - i)的最大乘積猾漫；否則選擇和為(n - i)的最大乘積，所以**定義dp[i]表示和為i的最大乘積感凤，則dp[i] = max{ max{i - x, dp[i - x]} * max{x, dp[x]}悯周，其中i > x >= i/2 } **
四、代碼
class Solution {
public:
int getMax(int a, int b){
return a > b ? a : b;
}
int integerBreak(int n) {
int *dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
int max;
for (int i = 2; i <= n; ++i) {
max = -1;
for (int j = i - 1; j >= i / 2; --j) {
max = getMax(max, (j > dp[j] ? j : dp[j]) * (i - j > dp[i - j] ? (i - j) : dp[i - j]));
}
dp[i] = max;
}
int res = dp[n];
delete[] dp;
return res;
}
};
