剪繩子

給你一根長(zhǎng)度為n的繩子，請(qǐng)把繩子剪成整數(shù)長(zhǎng)的m段(m、n都是整數(shù)，n>1并且m>1,m<=n),每段繩子的長(zhǎng)度記為k[1],...k[m]。請(qǐng)問(wèn)k[1]*...*k[m]可能的最大乘積是多少？

例如，當(dāng)繩子的長(zhǎng)度為8時(shí)，我們把它剪成長(zhǎng)度分別為2、3、3的三段，此時(shí)得到的最大乘積是18.

貪心法

    public int cutRope(int target){
        //4     2*2
        //5     2*3
        //6     3*3
        //7     2*2*3   4*3
        //8     2*3*3
        //9     3*3*3
        //10    2*2*3*3 4*3*3
        //11    2*3*3*3
        //由以上舉的例子可以看出，最后情況只可能為2或3
        //由3(n-3)>=2(n-2)，可知當(dāng)n=5時(shí)，等式相等，當(dāng)n>5時(shí)，應(yīng)讓3盡量的多。
        if(target<2){
            return 0;
        }
        if(target==2){
            //由題目知m>1,所以2為1*1=1
            return 1;
        }
        if(target==3){
            //m>1,所以3為2*1=1
            return 2;
        }
        if(target%3==0){
            //當(dāng)繩子長(zhǎng)剛好為3的倍數(shù)，則結(jié)果為3的（target/3）次冪
            return (int)Math.pow(3,target/3);
        }else if(target%3==1){
            //當(dāng)繩子長(zhǎng)對(duì)3取余剛好等于1時(shí)，可以多留出一個(gè)3，結(jié)果就為3的（target/3-1）次冪乘以4
            return 4*(int)Math.pow(3,target/3-1);
        }else{
            //當(dāng)繩子長(zhǎng)對(duì)3取余剛好等于2時(shí)，留出2，結(jié)果就為3的（target/3）次冪乘以2
            return 2*(int)Math.pow(3,target/3);
        }
    }
    public static void main(String[] args) {
        System.out.println(cutRope(8));//18
        System.out.println(cutRope(9));//27
    }

動(dòng)態(tài)規(guī)劃法

    //一個(gè)比較簡(jiǎn)單的動(dòng)態(tài)規(guī)劃
    //求問(wèn)題最優(yōu)解，該問(wèn)題可以分成若干個(gè)子問(wèn)題，子問(wèn)題之間還有重疊的更小的子問(wèn)題，考慮使用動(dòng)態(tài)規(guī)劃。
    //以自上而下分析，在長(zhǎng)度為n的繩子剪下乘積為f(n),剪下i長(zhǎng)度后，還剩n-i，即得公式
    //f(n)=max(f(i)*f(n-i))
    //為了避免重復(fù)計(jì)算子問(wèn)題，以從下往上的順序計(jì)算小問(wèn)題的解并保存下來(lái)，在以此為基礎(chǔ)求解更大問(wèn)題。
    //每
    public int cutRope(int target){
        if(target<2){
            return 0;
        }
        if(target==2){
            return 1;
        }
        if(target==3){
            return 2;
        }
        int []dp=new int[target+1];
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;//1 2 3 都是不剪繩子，得到的乘積最大
        int res=0;//記錄每次剪完的最大值
        for (int i=4;i<=target;i++){
            for (int j=1;j<=i/2;j++){//要計(jì)算j*i-j的最大值，所以只用計(jì)算j<=i的值
                res=Math.max(res,dp[j]*dp[i-j]);//得到長(zhǎng)度為i時(shí)，所有剪法的最大值
            }
            dp[i]=res;//得到當(dāng)前剪法的最大值，保存到dp數(shù)組中
        }
        return dp[target];//返回最大值
    }
    public static void main(String[] args) {
        System.out.println(cutRope(8));//18
        System.out.println(cutRope(9));//27
    }