題目14：剪繩子
給定一根長(zhǎng)度為n的繩子，請(qǐng)把繩子剪成m段（m糜俗、n都是整數(shù)，n>1并且m>1），每段繩子的長(zhǎng)度記為k[0],k[1],…,k[m]悠抹。
請(qǐng)問(wèn)k[0]* k[1] * … *k[m]可能的最大乘積是多少珠月？
舉例說(shuō)明
例如，當(dāng)繩子的長(zhǎng)度是8時(shí)锌钮，我們把它剪成長(zhǎng)度分別為2桥温、3、3的三段梁丘，此時(shí)得到的最大乘積是18侵浸。
思路
一. 基于動(dòng)態(tài)規(guī)劃
1. 自頂向下，得到公式
首先定義函數(shù)f(n)為把長(zhǎng)度為n的繩子剪成若干段后各段長(zhǎng)度乘積的最大值氛谜。在剪第一刀時(shí)掏觉，我們有n-1種選擇，也就是說(shuō)第一段繩子的可能長(zhǎng)度分別為1,2,3.....值漫，n-1澳腹。因此
f(n)=max(f(i)*f(n-i))，其中0<i<n
這是一個(gè)自上而下的遞歸公式杨何。
2. 自底向上酱塔，得到base case
由于遞歸會(huì)有大量的不必要的重復(fù)計(jì)算。一個(gè)更好的辦法是按照從下而上的順序計(jì)算危虱，也就是說(shuō)我們先得到f(2),f(3)羊娃，再得到f(4),f(5)，直到得到f(n)埃跷。
eg. 當(dāng)繩子的長(zhǎng)度為2的時(shí)候蕊玷，只能剪成長(zhǎng)度為1的兩段，所以f(2) = 1弥雹，當(dāng)n = 3時(shí)垃帅，容易得出f(3) = 2
代碼實(shí)現(xiàn)
public class _14 {
public static int maxAfterCutting(int length) {
if (length < 2)
return 0;
if (length == 2)
return 1;
if (length == 3)
return 2;
// 子問(wèn)題的最優(yōu)解存儲(chǔ)在f數(shù)組中，數(shù)組中的第i個(gè)元素表示把長(zhǎng)度為i的繩子剪成若干段后各段長(zhǎng)度乘積的最大值剪勿。
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++) {//最少剪一刀贸诚，所以內(nèi)層循環(huán)從j= 1開始
int num = f[j] * f[i - j];//分別計(jì)算f(j)*f(i-j)的值
if (max < num) {//并且與當(dāng)前記錄的最大值max進(jìn)行比較
max = num;
}
f[i] = max;
}
}
result = f[length];
return result;
}
public static void main(String[] args) {
System.out.println("長(zhǎng)度18的繩子的最大子乘積是："+maxAfterCutting(8));
}
}
輸出：
長(zhǎng)度為8的繩子的最大子乘積是：18
二.基于貪心
- 當(dāng)n<5時(shí)，我們會(huì)發(fā)現(xiàn)厕吉，無(wú)論怎么剪切赦颇，乘積product <= n，n為4時(shí)赴涵，product最大為2*2=4媒怯；
- 當(dāng)n>=5時(shí)，可以證明
2(n-2)>n
3(n-3)>n
3(n-3)>=2(n-2)
所以我們應(yīng)該盡可能地多剪長(zhǎng)度為3的繩子段髓窜。
代碼實(shí)現(xiàn)
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("長(zhǎng)度為8的繩子的最大子乘積是：" + maxAfterCutting(8));
}
}
輸出：
長(zhǎng)度為8的繩子的最大子乘積是：18
