剪绳子

给你一根长度为n的绳子，请把绳子剪成整数长的m段(m、n都是整数，n>1并且m>1,m<=n),每段绳子的长度记为k[1],...k[m]。请问k[1]*...*k[m]可能的最大乘积是多少？

例如，当绳子的长度为8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是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)，可知当n=5时，等式相等，当n>5时，应让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){
            //当绳子长刚好为3的倍数，则结果为3的（target/3）次幂
            return (int)Math.pow(3,target/3);
        }else if(target%3==1){
            //当绳子长对3取余刚好等于1时，可以多留出一个3，结果就为3的（target/3-1）次幂乘以4
            return 4*(int)Math.pow(3,target/3-1);
        }else{
            //当绳子长对3取余刚好等于2时，留出2，结果就为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
    }

动态规划法

    //一个比较简单的动态规划
    //求问题最优解，该问题可以分成若干个子问题，子问题之间还有重叠的更小的子问题，考虑使用动态规划。
    //以自上而下分析，在长度为n的绳子剪下乘积为f(n),剪下i长度后，还剩n-i，即得公式
    //f(n)=max(f(i)*f(n-i))
    //为了避免重复计算子问题，以从下往上的顺序计算小问题的解并保存下来，在以此为基础求解更大问题。
    //每
    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*i-j的最大值，所以只用计算j<=i的值
                res=Math.max(res,dp[j]*dp[i-j]);//得到长度为i时，所有剪法的最大值
            }
            dp[i]=res;//得到当前剪法的最大值，保存到dp数组中
        }
        return dp[target];//返回最大值
    }
    public static void main(String[] args) {
        System.out.println(cutRope(8));//18
        System.out.println(cutRope(9));//27
    }