描述：給你一根長度為n的繩子，請把繩子剪成m段(m和n均為正整數，且m>1,n>1),每段繩子的長度記為a1、a2、a3、a4....an 現要求a1*a2*a3*a4*...*an的乘積最大，例如當繩子n的長度為8時，我們把它分成2、3、3三段這樣得到的乘積也是最大的乘積18。
動态規劃：當繩子長度為n時，我們剪第一刀有n-1種可能，因為第一刀可以剪1米、2米、3米....n-1米。是以f(n) = max(f(i) * f(n - i))，其中0 < i < n。根據描述我們能寫出如下代碼：
public static int cut(int length) {
if(length < 2) {
return 0;
}
if(length == 2) {
return 1;
}
if(length == 3) {
return 2;
}
int[] storage = new int[length + 1];
// 初始化、這四個存的不是最優解而是用于計算的參數
storage[0] = 0;
storage[1] = 1;
storage[2] = 2;
storage[3] = 3;
// 定義一個變量來存儲最大值
int max = 0;
// 從第四米開始storage存的是最優解
for (int i = 4; i <= length; i++) {
// 從小到大開始把每個子問題最優解存在數組裡
for (int j = 1; j <= i / 2; j++) {
int multiply = storage[j] * storage[i - j];
if (multiply > max) {
max = multiply;
}
}
storage[i] = max;
}
return storage[length];
} 複制
貪心：如果我們按照下面這種政策來剪繩子，則得到的各段繩子的長度乘積最大：當n>=5時，我們盡可能的多剪長度為3的繩子，當剩下的繩子長度為4時，就把繩子剪成2段長為2的，比如長為7的繩子我們剪成3 * 2 * 2這樣得到最大值為12。
public static int cut(int length) {
if(length < 2) {
return 0;
}
if(length == 2) {
return 1;
}
if(length == 3) {
return 2;
}
// 記錄要剪成3m一段的段數
int three = length / 3;
// 餘下1m說明要騰出來一段湊4m來剪兩個2m
if (length - three * 3 == 1) {
// 騰出
three--;
}
// 要剪成2m的段數
int two = (length - three * 3) / 2;
return (int)(Math.pow(3,three) * Math.pow(2,two));
} 複制
如此看來貪心算法能很快得到答案，但是需要紮實的數學功底。