题目描述
给定一根长度为n的绳子，请把绳子剪成m段，每段绳子记为k[0],k[1]……k[m]。请问k[0]*k[1]……*k[m]可能的最大乘积是多少？例如：当绳子长度为8时，我们把它剪成长度分别为2,3,3段，此时最大乘积为18.
解题思路
先用常规的需要O(n^2)时间和O(n)空间的动态规划的思路，接着用只需要O(1)时间和空间的贪婪算法来分析解决这个问题。
动态规划
首先定义函数f(n)为把长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀的时候，我们有n-1种可能的选择，也就是剪出来的第一段绳子的可能长度为1，2，…n-1。因此f(n)=max(f(i)xf(n-i))，其中0<i<n.
这是一个从上至下的递归公式。由于递归会有很多重复的子问题，从而有大量不必要的重复计算。一个更好的办法是按照从下而上的顺序计算，也就是说我们先得到f(2)、f(3)，再得到f(4)、f(5)，直到得到f(n)。 当绳子的长度为2时，只可能剪成长度为1的两段，因此f(2)等于1.当绳子的长度为3时，可能把绳子剪成长度为1和2的两段或者长度都为1的三段，由于1x2>1x1x1，因此f(3)=2
贪心算法 当n = 4时，最大乘积就是4. 当n >= 5时，尽可能多剪长度为3的绳子，当剩下为4的时候，就剪成两段2 也就是说，n>=5时，最大乘积都由若干个3，最多两个2构成的 证明很简单： n >= 5时，3(n-3) >= 2(n-2) > n
算法图解
自我感觉还是重点理解这个动态规划吧，对于后面的贪心如果面试换题，可能一时也想不出来！
代码里面有几个不好理解的点：
i / 2
上到下和下到上都涉及了一个i/2，这个东西的实质意义也就是保证计算了14不会再计算41这样的过程
product[1] = 1; product[2] = 2; product[3] = 3;
这段实质上是为后面第二个for循环方便处理的。虽然 product[i]记录的是长度为i的最大值，但在这一小段并不是这个含义。而是再计算 product[4]的时候去找这里面的能求出最大值的组合。如product[1]*product[3] product[2]*product[2]。在product[4]往后则都是记录的最优解。
对于长度为1，2，3
直接给出了最优解分别是0，1，2。注意和上面这个存放最优解的数组区分。
参考代码：
package offer
;
import static java
.lang
.StrictMath
.pow
;
public class Offer14 {
public static void main(String
[] args
) {
int length
= 10;
System
.out
.println(maxProductAfterCuttingTtoD(length
));
System
.out
.println(maxProductAfterCuttingDtoT(length
));
System
.out
.println(maxProductAfterCuttingActive(length
));
}
static int maxProductAfterCuttingTtoD(int length
) {
int a
[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
if (length
< 2)
return 0;
if (length
== 2)
return 1;
if (length
== 3)
return 2;
int i
= 4;
while (i
<= length
) {
int j
= 1;
while (j
<= i
/ 2) {
if (a
[j
] * a
[i
- j
] > a
[i
])
a
[i
] = a
[j
] * a
[i
- j
];
j
++;
}
i
++;
}
return a
[length
];
}
private static int maxProductAfterCuttingActive(int length
) {
if (length
< 2) return 0;
else if (length
== 2) return 1;
else if (length
== 3) return 2;
else if (length
>= 4) {
int product
[] = new int[length
+ 1];
product
[0] = 0;
product
[1] = 1;
product
[2] = 2;
product
[3] = 3;
int max
= 0;
for (int i
= 4; i
<= length
; ++i
) {
max
= 0;
for (int j
= 1; j
<= i
/ 2; ++j
)
{
if (max
< product
[j
] * product
[i
- j
])
max
= product
[j
] * product
[i
- j
];
}
product
[i
] = max
;
}
return product
[length
];
}
return 0;
}
private static int maxProductAfterCuttingDtoT(int length
) {
if (length
< 2)
return 0;
if (length
== 2)
return 1;
if (length
== 3)
return 2;
int timesOf3
= length
/ 3;
if ((length
- timesOf3
* 3) == 1)
timesOf3
= timesOf3
- 1;
int timesOf2
= (length
- timesOf3
* 3) / 2;
return ((int) (pow(3, timesOf3
)) * ((int) pow(2, timesOf2
)));
}
}
附录
该题源码在我的 ?Github 上面！
