05 August 2008
给一个正整数n，分成k个正整数，k个正整数加起来等于n，同时保证k个正整数的乘积最大，返回这个乘积
dp[i]表示当 总值为i的时候，可以求得的最大组合乘积。
i=6,dp[6]则表示凑成和为6的大于俩个数的乘积最大值
因此我们的目的是求dp这个数组，返回dp[n]
对于每一个i，枚举它的可能组成(其中j < i)，拆成俩个数的乘积就是j * (i-j)，而拆成多个数的乘积则是(i - j) * dp[i - j] 然后取得这些枚举位置中的最大结果，保存为dp[i]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public static int integerBreak(int n) {
int[] dp = new int[n + 1];
//dp[0] = dp[1] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i] = Math.max(dp[i], Math.max((i - j) * dp[j], (i - j) * j));
}
}
return dp[n];
}
}