14_剪绳子

要求：给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，n>1并且m≥1）。每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1]…*k[m]可能的最大乘积是多少？例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。
时间复杂度：O(n^2)
空间复杂度：O(n)
思路：
1、使用动态规划：先自上而下分析，在长度为n的绳子所求为f(n)，剪下一刀后剩下的两段长度是i和n-i，在这个上面还可能继续减(子问题)，所以状态转移方程为：
然后自下而上的解决问题，可以从f(1)开始向上计算并打表保存，最终获得f(n)的值。

 // 动态规划
    public static int cutRope(int length){
        if(length < 2)//因为要求长度n>1,所以这里返回0表示输入非法
        {return 0;}
        if(length == 2)//长度为2时,因为要求剪下段数m>1,所以最大是1x1=1
        {return 1;}
        if(length == 3)//长度为3时,因为要求剪下段数m>1,所以最大是1x2=2
        {return 2;}

        //运行至此,说明绳子的长度是>3的,这之后0/1/2/3这种子问题最大就是其自身长度
        //而不再需要考虑剪一刀的问题,因为它们剪一刀没有不剪来的收益高
        //而在当下这么长的绳子上剪过才可能生成0/1/2/3这种长度的绳子,它们不需要再减
        //所以下面的表中可以看到它们作为子问题的值和上面实际返回的是不一样的

        //在表中先打上子绳子的最大乘积
        int[] products = new int[length + 1];
        products[0] = 0;
        products[1] = 1;
        products[2] = 2;
        products[3] = 3;//到3为止都是不剪最好

        int max = 0;//用于记录最大乘积
        //对于4以上的情况,每次循环要求f(i)
        for(int i = 4; i <= length; ++i) {
            max = 0;//每次将最大乘积清空
            //因为要计算f(j)乘以f(i-j)的最大值,j超过i的一半时是重复计算
            //所以只需要考虑j不超过i的一半的情况
            for(int j = 1; j <= i / 2; ++j) {
                //计算f(j)乘以f(i-j)
                int product = products[j] * products[i - j];
                //如果比当前找到的还大
                if(max < product)
                    max = product;//就把最大值更新
            }
            //这里是循环无关的,书上在for里面,我把它提出来
            products[i] = max;//最终,更新表中的f(i)=max(f(j)·f(i-j))
        }
        //循环结束后,所求的f(length)也就求出来了
        max = products[length];//将其记录下来以在销毁后能返回
        return max;
    }

2、贪心算法:应把绳子剪成尽量多的3，让剩下的都是2这样的组合。

public static int cutRopetx(int length){
        if(length < 2)//因为要求长度n>1,所以这里返回0表示输入非法
        {return 0;}
        if(length == 2)//长度为2时,因为要求剪下段数m>1,所以最大是1x1=1
        {return 1;}
        if(length == 3)//长度为3时,因为要求剪下段数m>1,所以最大是1x2=2
        {return 2;}
        //尽可能多地减去长度为3的绳子段,这里是计算一下能减出多少个3
        int timeOf3 = length/3;
        //当绳子最后剩下的长度为4的时候,不能再剪去长度为3的绳子段。
        //此时更好的方法是把绳子剪成长度为2的两段,因为2*2>3*1。
        if(length-timeOf3*3 == 1){//如果最后只剩一个1
            timeOf3 -=1;//就要留下一个3
        }
        //保证剩下的一定是4或者2或者0,计算一下能剪出几个2来(只有2/1/0三种情况)
        int timeOf2 = (length-timeOf3*3)/2;
        int result = 1;
        for(int i=0; i<timeOf3; i++){
            result = result*3;
        }
        for(int j=0; j<timeOf2;j++){
            result = result*2;
        }
        return result;

    }