题目大意：
整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=343
解题思路分析：
本题的关键是如何拆分数字能使得结果最大化，对于这种无法直观的看出拆分办法的题目，最有效的解决方案即是一种一种的尝试，通过不断的尝试找到最优解。对于一个大于等于2的正整数n，我们至少能将其拆分成为2部分：x, y，其中x+y=n，如果x和y仍大于等于2，我们仍可以将其继续拆分。这是一个典型的递归思路，我们定义一个递归函数help(n)，参数n为当前数字，函数中，我们循环每种拆分方式将该数字分成2部分，循环时，我们可以将当前数字变成1和n-1，2和n-2，3和n-3 … 直到n-1和1。举个例子，比如数字8，可以拆分的方式为：1+7, 2+6, 3+5, 4+4, 5+3, 6+2, 7+1。这里有一处可以优化的地方，我们发现上述的拆分方式中有一些重复的地方，比如1+7和7+1，因此，我们循环时只要循环到当前数字的一半即可（只需要1+7, 2+6, 3+5, 4+4这部分）。
对于上面的每种拆分，我们可以得到2个数字，比如3和5，如果这两个数字大于等于2，说明还可以继续拆分，但拆分后的结果并不一定优于当前数字，因此，对于拆分后的某个数字x，它的最优值应该是，max(x, help(x))。进而，对于当前数字n而言，它的拆分最优解应该是： max(x, help(x)) * max(y, help(y))。 保证x+y=n。
实现代码：
int[] memo; // 记忆数组
public int integerBreak(int n) {
memo=new int[n+1]; // 初始化记忆数组
return help(n); // 递归求解
}
int help(int n){
// 如果n小于等于2，返回1
if(n<=2) return 1;
// 如果记忆数组中存在该解，直接返回
if(memo[n]>0) return memo[n];
// 返回结果
int res=0;
// 循环每种拆分情况
for(int i=1;i<=n/2;i++){
// 得到左边最大值
int maxLeft=Math.max(i, help(i));
// 得到右边最大值
int maxRight=Math.max(n-i, help(n-i));
// 更新当前数字拆分后乘积的最大值
res=Math.max(res, maxLeft*maxRight);
}
// 将当前数字最优解存入记忆数组
memo[n]=res;
return res;
} 本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Integer Break.
Memory Usage: 33.1 MB, less than 14.29% of Java online submissions for Integer Break.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-343-integer-break-解题思路分析/