67 剑指offer---剪绳子

                                                  剪绳子

题目描述

给你一根长度为n的绳子,请把绳子剪成整数长的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

输入描述:

输入一个数n,意义见题面。(2 <= n <= 60)

输出描述:

输出答案。

示例1

输入

8

输出

18

贪心算法

n<2时,返回0;n=2时,返回1;n=3时,返回2
根据数学计算,当n>=5时,2(n-2)>n,3(n-3)>n,这就是说,将绳子剪成2和(n-2)或者剪成3和(n-3)时,乘积大于不剪的乘积,因此需要把绳子剪成2或者3。并且3(n-3)>=2(n-2),也就是说,当n>=5时,应该剪尽量多的3,可以使最后的乘积最大。对于长度是n的绳子,我们可以剪出n/3个3,剩余长度是1或者2,如果余数是1,就可以把1和最后一个3合并成4,那么4剪出两个2得到的乘积是4,比1*3大,因此这种情况下,需要将3的个数减少1,变成两个2;如果余数是2,那么无需做修改。
可以得到最大的乘积是:3^timesOf3 * 2^timesOf2;
 

public int cutRope(int length) {
        if(length < 2)
        {
            return 0;
        }
        if(length == 2)
        {
            return 1;
        }
        if(length == 3)
        {
            return 2;
        }
        // 尽可能多地减去长度为3的绳子段
        int timesOf3 = length / 3;

        // 当绳子最后剩下的长度为4的时候,不能再剪去长度为3的绳子段。
        // 此时更好的方法是把绳子剪成长度为2的两段,因为2*2 > 3*1。
        if(length - timesOf3 * 3 == 1)
        {
            timesOf3 -= 1;
        }
        int timesOf2 = (length - timesOf3 * 3) / 2;

        return (int) (pow(3, timesOf3)) * (int) (pow(2, timesOf2));
    }

动态规划

此问题明显包含独立的子问题,用f(n)表示长度为n的绳子剪完后的最大乘积,则可以写出递推公式

f(n) = max{f(n-i) × f(i)}, 0 < i < n

因为自下而上的时间复杂度为O(n), 每次递推时要对i循环O(n) ,所以时间复杂度是O(n2) 

我们对长度为8的绳子进行模拟。

f(4) = f(2) * f(2) = 4;

f(5) = f(2) * f(3) = 6;

f(6) = f(3) * f(3) = 9;

f(7) = f(3) * f(4) = f(2) * f(5) = 12;

f(8) = f(3) * f(5) = 18;

public int cutRope(int length) {
        if(length < 2) {
            return 0;
        }
        if(length == 2) {
            return 1;
        }
        if(length == 3) {
            return 2;
        }
        int[] products = new int[length + 1];
        products[0] = 0;
        products[1] = 1;
        products[2] = 2;
        products[3] = 3;
        
        int max = 0;
        for(int i = 4; i <= length; ++i) {
            max = 0;
            for(int j = 1; j <= i / 2; ++j) {
                int product = products[j] * products[i - j];
                if(max < product) {
                    max = product;
                }
                products[i] = max;
            }
        }

        max = products[length];
        return max;
    }

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 18:13
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 17:37
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务