本文共 1490 字，大约阅读时间需要 4 分钟。
问题描述：给定一个正整数 n，将其分解为至少两个正整数的总和并最大化这些整数的乘积。返回您可以得到的最大结果。
例如，给定 n = 2，返回 1 (2 = 1 + 1)； 给定 n = 10，返回 36 (10 = 3 + 3 + 4)。 注： 您可能认为 n 不小于2且不大于58。算法分析
根据题目设定的条件整数n的取值范围为： 2<=n<=58
分析一下： 当n=2时： n=1+1; result = 1*1=1 当n=3时： 可以拆分为: 1+2 或者 1+1+1，但是显然拆分为 1+2，所获得的乘积最大 当n=4时：可以拆分为： 1+3 或者 2+2，但是显然拆分为 2+2，所获得的乘积最大 当n=5时：可以拆分为：2+3，所获得乘积最大 当n=6时：可以拆分为：3+3，所获得乘积最大 当n=7时：可以拆分为：3+4，所获得乘积最大 当n=8时：可以拆分为：3+3+2，所获得乘积最大 当n=9时：可以拆分为：3+3+3，所获得乘积最大 当n=10时：可以拆分为：3+3+4，所获得乘积最大 通过观察上述内容，我们可以发现从n=5开始，拆分的结果都有数字3。 之后的数字，例如11，可以先拆出来1个3，然后再看余下的8如何拆分。算法设计
public static int interBreakProblem(int n) { if(n==2 || n==3) return n-1; if(n==4) return n; int result=1; while(n>4) { result*=3; n-=3; } return result*n; } 算法设计2：采用DP
当采用DP时，最主要是要推倒出来状态方程：
public static int integerBreak(int n) { int[] dp = new int[n + 1]; dp[1] = 1; for(int i = 2; i <= n; i ++) { for(int j = 1; j < i; j ++) { dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j]))); } } return dp[n]; } 可以进行上述方法测试：
public static void main(String[] args) { // TODO Auto-generated method stub int n=11; int result=integerBreak(n); System.out.println("RESULT IS: "+result); int res=interBreakProblem(n); System.out.println("RESULT IS: "+res); } 执行结果：
RESULT IS: 54
RESULT IS: 54以上两个方法执行结果相同。相互验证。
（完）
转载地址：http://ogvdi.baihongyu.com/