题目:
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: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Note: You may assume that n is not less than 2 and not larger than 58.
假设N为4
先使用记忆化搜索的自顶向下的递归解法:
public class P343IntegerBreak {
public int integerBreak(int n) {
return digui(n);
}
// 求解的是分解n的最优乘积.
private int digui(int n) {
if (n == 1) {
return 1;
}
int max = -1;
for (int i = 1; i < n; i++) {
max = Math.max(max, i * digui(n - i));
max = Math.max(max, i * (n - i));
}
return max;
}
public static void main(String[] args) {
int n = 10;
P343IntegerBreak p = new P343IntegerBreak();
int i = p.integerBreak(n);
System.out.println(i);
}
}
从图里面其实可以看到比如分解2最大的乘积实际上会被多计算几次的,因此实际上可以记录下来他的值,防止重复计算。开辟一个大小为n的数组进行保存。代码如下:
public class P343IntegerBreakV2 {
int[] tmp;
public int integerBreak(int n) {
tmp = new int[n+1];
for (int i = 0; i < n+1; i++) {
tmp[i] = -1;
}
return digui(n);
}
// 求解的是分解n的最优乘积.
private int digui(int n) {
if (n == 1) {
return 1;
}
if (tmp[n] != -1) {
return tmp[n];
}
int max = -1;
for (int i = 1; i < n; i++) {
max = Math.max(max, i * digui(n - i));
max = Math.max(max, i * (n - i));
}
tmp[n] = max;
return max;
}
public static void main(String[] args) {
int n = 2;
P343IntegerBreakV2 p = new P343IntegerBreakV2();
long start = System.currentTimeMillis();
int i = p.integerBreak(n);
System.out.println(i);
System.out.println("cost time = " + (System.currentTimeMillis() - start));
}
}
如果使用自底向上的动态规划算法的话,代码如下:
public class P343IntegerBreakV3 {
// 存储分解数字n(分解成2部分)的最大乘积和。
int[] tmp;
public int integerBreak(int n) {
tmp = new int[n+1];
for (int i = 0; i < n+1; i++) {
tmp[i] = -1;
}
tmp[1] = 1;
for (int i = 1; i <= n; i++) {
// 将数字i 分解为 j + (i-j)
for (int j = 1; j < i; j++) {
tmp[i] = Math.max(j * (i - j),Math.max(tmp[i], j * tmp[i-j]));
}
}
return tmp[n];
}
public static void main(String[] args) {
int n = 10;
P343IntegerBreakV3 p = new P343IntegerBreakV3();
long start = System.currentTimeMillis();
int i = p.integerBreak(n);
System.out.println(i);
System.out.println("cost time = " + (System.currentTimeMillis() - start));
}
}