14:剪绳子

发表于 | 分类于

题目14：剪绳子

给定一根长度为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。

思路

一. 基于动态规划

1. 自顶向下，得到公式
首先定义函数f(n)为把长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀时，我们有n-1种选择，也就是说第一段绳子的可能长度分别为1,2,3…..，n-1。因此
f(n)=max(f(i)*f(n-i))，其中0<i<n
这是一个自上而下的递归公式。

2. 自底向上，得到base case
由于递归会有大量的不必要的重复计算。一个更好的办法是按照从下而上的顺序计算，也就是说我们先得到f(2),f(3)，再得到f(4),f(5)，直到得到f(n)。
eg. 当绳子的长度为2的时候，只能剪成长度为1的两段，所以f(2) = 1，当n = 3时，容易得出f(3) = 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
public class _14 {
	public static int maxAfterCutting(int length) {
		if (length < 2)
			return 0;
		if (length == 2)
			return 1;
		if (length == 3)
			return 2;
		// 子问题的最优解存储在f数组中，数组中的第i个元素表示把长度为i的绳子剪成若干段后各段长度乘积的最大值。
		int[] f = new int[length + 1];
		f[0] = 0;
		f[1] = 1;
		f[2] = 2;//base case
		f[3] = 3;//base case
		int result = 0;
		for (int i = 4; i <= length; i++) {
			int max = 0;
			for (int j = 1; j <= i / 2; j++) {//最少剪一刀，所以内层循环从j= 1开始
				int num = f[j] * f[i - j];//分别计算f(j)*f(i-j)的值
				if (max < num) {//并且与当前记录的最大值max进行比较
					max = num;
				}
				f[i] = max;
			}
		}
		result = f[length];
		return result;
	}
	public static void main(String[] args) {
		System.out.println("长度18的绳子的最大子乘积是："+maxAfterCutting(8));
	}
}

输出：

1
长度为8的绳子的最大子乘积是：18

二.基于贪心

  1. 当n<5时，我们会发现，无论怎么剪切，乘积product <= n，n为4时，product最大为2*2=4；
  2. 当n>=5时，可以证明
    2(n-2)>n
    3(n-3)>n
    3(n-3)>=2(n-2)

所以我们应该尽可能地多剪长度为3的绳子段。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class _14 {
	public static int maxAfterCutting(int n) {
		if (n < 2) {
			return 0;
		}
		if (n == 2) {
			return 1;
		}
		if (n == 3) {
			return 2;
		}
		int timesOf3 = n / 3;
		if (n - timesOf3 * 3 == 1) {
			timesOf3--;
		}
		int timesOf2 = (n - timesOf3 * 3) / 2;
		return (int) (Math.pow(3, timesOf3)) * (int) (Math.pow(2, timesOf2));
	}

	public static void main(String[] args) {
		System.out.println("长度为8的绳子的最大子乘积是：" + maxAfterCutting(8));
	}
}

输出：

1
长度为8的绳子的最大子乘积是：18
> >