343 Integer Break
Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.
Return the maximum product you can get.
Example 1:
Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
动态规划解法：
dp[i] 表示整数 i 分解为整数的最大乘积（可以不分解，无视 k>=2 的条件），最大乘积最后分解的结果只有 2 和 3 ，先指定 dp[2]=2 , dp[3]=3 ，其余的为 2*dp[i-2] 和 3*dp[i-3] 较大者。同时考虑 n 为 2 和 3 的 corner case 。时间复杂度 o(n) ，空间复杂度 o(n)
public int integerBreak(int n) {
if(n<=3) return n-1;
int[] dp=new int[n+1];
dp[2]=2;
dp[3]=3;
for(int i=4;i<=n;++i){
int i2=2*dp[i-2];
int i3=3*dp[i-3];
dp[i]=Math.max(i2,i3);
}
return dp[n];
}
class Solution {
public:
int integerBreak(int n) {
if(n<=3) return n-1;
int dp[n+1];
dp[1]=1;
dp[2]=2;
dp[3]=3;
for(int i=4;i<=n;++i){
int i1=2*dp[i-2];
int i2=3*dp[i-3];
if(i1>i2) dp[i]=i1;
else dp[i]=i2;
}
return dp[n];
}
};
最优解：贪心算法
尽可能多分解为 3 ，但如果除以 3 余 1 ，需要少一个 3 ，因为 3 乘以 1 小于 2 乘以 2 。时间复杂度 o(log n) ，空间复杂度 o(1)
public int integerBreak(int n) {
if(n<=3) return n-1;
int count3=n/3;
if(n%3==1){
return 4*(int)Math.pow(3,count3-1);
} else if(n%3==2){
return 2*(int)Math.pow(3,count3);
} else {
return (int)Math.pow(3,count3);
}
}