本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖

面試題14：剪繩子

題目要求：
給你一根長度為n的繩子，請把繩子剪成m段，記每段繩子長度為k[0],k[1]...k[m-1],求k[0]k[1]...k[m-1]的最大值。已知繩子長度n為整數(shù)，m>1(至少要剪一刀，不能不剪)，k[0],k[1]...k[m-1]均要求為整數(shù)。
例如，繩子長度為8時，把它剪成3-3-2，得到最大乘積18；繩子長度為3時，把它剪成2-1，得到最大乘積2。

解題思路：
本題有動態(tài)規(guī)劃算法的幾個明顯特征：
（1）是求最優(yōu)解問題，如最大值，最小值；
（2）該問題能夠分解成若干個子問題，并且子問題之間有重疊的更小子問題。
通常按照如下4個步驟來設(shè)計(jì)一個動態(tài)規(guī)劃算法：
（1）刻畫一個最優(yōu)解的結(jié)構(gòu)特征；
（2）遞歸地定義最優(yōu)解的值；
（3）計(jì)算最優(yōu)解的值，通常采用自底向上的方法；
（4）利用計(jì)算出的信息構(gòu)造一個最優(yōu)解。
以此題為例，我們定義長度為n的繩子剪切后的最大乘積為f(n),剪了一刀后,f(n)=max(f(i)*f(n-i));假設(shè)n為10，第一刀之后分為了4-6，而6也可能再分成2-4（6的最大是3-3，但過程中還是要比較2-4這種情況的），而上一步4-6中也需要求長度為4的問題的最大值，可見，各個子問題之間是有重疊的，所以可以先計(jì)算小問題，存儲下每個小問題的結(jié)果，逐步往上，求得大問題的最優(yōu)解。

package chapter2;
/**
 * Created by ryder on 2017/7/5.
 * 剪繩子
 */
public class P96_CuttingRope {
    public static int maxCutting(int length){
        if(length<2) return 0;
        if(length==2)return 1;
        if(length==3)return 2;
        int[] dp = new int[length+1];
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        int max = 0;
        int temp = 0;
        for(int i=4;i<=length;i++){
            max = 0;
            for(int j=1;j<=i/2;j++){
                temp = dp[j]*dp[i-j];
                if(temp>max)
                    max = temp;
            }
            dp[i] = max;
        }
        return dp[length];
    }
    public static void main(String[] args){
        for(int i=2;i<10;i++){
            System.out.println("長度為"+i+"的最大值->"+maxCutting(i));
        }
    }
}

運(yùn)行結(jié)果

長度為2的最大值->1
長度為3的最大值->2
長度為4的最大值->4
長度為5的最大值->6
長度為6的最大值->9
長度為7的最大值->12
長度為8的最大值->18
長度為9的最大值->27

上述算法的時間復(fù)雜度為o(n^2);但其實(shí)，可以使用貪婪算法在o(1)時間內(nèi)得到答案：n<5時，和動態(tài)規(guī)劃一樣特殊處理；n>=5時，盡可能多地剪長度為3的繩子，當(dāng)剩下的繩子長度為4時，剪成2-2；比如長度為13的繩子， 剪成3-3-3-2-2；貪婪算法雖然快，但一般都思路奇特，可遇不可求。且面試官一般都會要求證明，數(shù)學(xué)功底要好 。