题目
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
Example 1:
Input: 2Output: 1Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: 10Output: 36Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Note: You may assume that n is not less than 2 and not larger than 58.
解法思路（一）
怎么分解一个正整数呢？
5 可以分解成：[1, 4], [2, 3], [3, 2], [4, 1]，这是分解树的第一层；4, 3, 2 这些树又可以继续向下分；整个递归树从根节点到叶子节点的路径 + 第一层的分解，构成了 n 的所有分解；
解法的演进
递归（从上到下）；记忆化递归（从上到下）；动态规划（从下到上）；
解法实现（一）递归
关键字
递归 正整数分解
实现细节
package leetcode._343;
public class Solution343_1 {
public int integerBreak(int n) {
if (n == 1) {
return 1;
}
int res = -1;
for (int i = 1; i <= n - 1; i++) {
res = max3(res, i * (n - i), i * integerBreak(n - i));
}
return res;
}
private int max3(int a, int b, int c) {
return Math.max(a, Math.max(b, c));
}
public static void main(String[] args) {
Solution343_1 s = new Solution343_1();
int res = s.integerBreak(29);
System.out.println(res);
}
}
解法实现（二） 记忆化递归
关键字
记忆化递归
实现细节
package leetcode._104;
import java.util.Arrays;
public class Solution104_2 {
private int[] memo;
private int res = -1;
public int integerBreak(int n) {
memo = new int[n + 1];
Arrays.fill(memo, -1);
return breaker(n);
}
private int breaker(int n) {
if (n == 1) {
return 1;
}
if (memo[n] != -1) {
return memo[n];
}
for (int i = 1; i <= n - 1; i++) {
res = max3(res, i * (n - i), i * breaker(n - i));
}
memo[n] = res;
return res;
}
private int max3(int a, int b, int c) {
return Math.max(a, Math.max(b, c));
}
public static void main(String[] args) {
Solution104_2 s = new Solution104_2();
int res = s.integerBreak(5);
System.out.println(res);
}
}
解法实现（三）动态规划
关键字
动态规划
实现细节
package leetcode._104;
import java.util.Arrays;
public class Solution104_3 {
private int[] memo;
public int integerBreak(int n) {
memo = new int[n + 1];
Arrays.fill(memo, -1);
memo[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i - 1; j++) {
memo[i] = max3(memo[i], j * (i - j), j * memo[i - j]);
}
}
return memo[n];
}
private int max3(int a, int b, int c) {
return Math.max(a, Math.max(b, c));
}
}
返回 LeetCode [Java] 目录
