Offer14（剪绳子）

发表于 | 分类于 ，

题目：

　　给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，n>1并且m≥1）。
每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1]…*k[m]可能的最大乘积是多少？
例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。

思路：

　　动态规划的关键是得出递推式，此题需要求绳子的最大乘积，因此设长度的为n的绳子剪成m段后的最大乘积为f(n)，而绳子上剪一刀有n-1种可能，因此
f(n)=max(f(i)*f(n-i)),得出递归式后，即可从下往上写出代码。写代码过程中需要先求出前几项的值存入数组中。
　　而此题贪心算法需要数学正面每次剪去长度为3的绳子，若剩下长度为4，每次剪长度为2的绳子时，所得乘积最大。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 动态规划
public static int maxProductAfterCutting2(int len) {
	if (len < 2) {
		return 0;
	}
	if (len == 2) {
		return 2;
	}
	if (len == 3) {
		return 2;
	}
	int[] maxProduct = new int[len+1];
	maxProduct[0] = 0;
	maxProduct[1] = 1;
	maxProduct[2] = 2;
	maxProduct[3] = 3;
	for(int i = 4;i <= len;i++) {
		int max = 0;
		for(int j = 1;j <= i/2;j++) {
			if (maxProduct[j]*maxProduct[i-j] > max) {
				max = maxProduct[j]*maxProduct[i-j];
			}
		}
		maxProduct[i] = max;
	}
	return maxProduct[len];
}
	//贪心算法
public static int maxProductAfterCutting1(int len) {
	if (len < 2) {
		return 0;
	}
	if (len == 2) {
		return 1;
	}
	if(len == 3) {
		return 2;
	}
	int timeof3 = len/3;
	if (len - timeof3*3 == 1) {
		timeof3--;
	}
	int timeof2 = (len-timeof3*3)/2;
	return (int) (Math.pow(3, timeof3)*Math.pow(2, timeof2));
}

复杂度分析：

动态规划：

　　时间复杂度：
　　　　O(n**2)。
　　空间复杂度：
　　　　O(n)。

贪心算法：

　　时间复杂度：
　　　　O(1)。
　　空间复杂度：
　　　　O(1)。