题目描述
原题地址：https://leetcode-cn.com/problems/integer-break/
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
解法1——递归
递归的思路无非就是自顶向上，很容易想出来，代码如下
//递归-自顶向下
public static int integerBreak(int n) {
return dfs(n);
}
public static int dfs(int n){
if(n == 1 || n == 2){
return 1;
}
int res = 0;
for(int i = 1;i < n;i++){
res = Math.max(res,Math.max(i * dfs(n - i),i * (n - i)));
}
return res;
}
这种方法虽然比较容易想出来，但是中间重复计算的非常多，实际在LeetCode中不能AC。
解法2——动态规划
动态规划那么就是自底向上的方法，根据上一步的递归，状态转移方程为
其中，为区间
之间的数。
//动态规划-自下向上
public static int integerBreak2(int n) {
int[] dp = new int[n + 1];
dp[2] = 1;
for(int i = 2;i <= n;i++){
for(int j = 1;j <= i - 1;j++){
dp[i] = Math.max(dp[i],Math.max(j * dp[i - j],j * (i - j)));
}
}
return dp[n];
}
解法3——数学分析
根据高中学习的均值不等式，可以得到
设，那么目标积为
对上述函数求导数，可以得到
当时取得最大值，那么离
最近的两个整数为
2和3，下面再来考虑时选择3还是选择2。
假设一个数，则乘积为
,对其两边取对数可以得到
由于，所以是
越大越好，所以应该尽可能的多取
3.
//数学方法
public static int integerBreak3(int n){
if(n == 2){
return 1;
}
if(n == 3){
return 2;
}
int res = 1;
while(n > 4){
res *= 3;
n -= 3;
}
return res * n;
}
