題目來源
把一個數(shù)拆分成多個數(shù)，使得其乘積最大墨闲。
一個方法是DP的方法今妄，這個DP遞推過程說實話我沒有想到，代碼如下：
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n+1);
dp[2] = 1;
for (int i=2; i<=n; i++)
for (int j=1; j<i; j++)
dp[i] = max(dp[i], max(dp[i-j], i-j) * max(dp[j], j));
return dp[n];
}
};
一個是利用數(shù)學知識證明鸳碧，只有當2盾鳞，或者3時候最大，并且2的個數(shù)不能大于兩個瞻离，因為2*2*2 < 3*3腾仅。
(N/2)*(N/2)>=N, then N>=4
(N-1)/2 *(N+1)/2>=N, then N>=5
These two expressions mean that factors should be less than 4, otherwise we can do the break and get a better product. The factors in last result should be 1, 2 or 3. Obviously, 1 should be abandoned. Thus, the factors of the perfect product should be 2 or 3.
class Solution {
public:
int integerBreak(int n) {
if (n == 2)
return 1;
if (n == 3)
return 2;
int product = 1;
while (n > 4) {
product *= 3;
n -= 3;
}
product *= n;
return product;
}
};
