【剑指offer】面试题14：剪绳子

落日映苍穹つ 2022-06-12 07:47 181阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1,m>1），  
每段绳子的长度记为 k\[0\], k\[1\], k\[2\], …, k\[m\]。  
请问 k\[0\] \* k\[1\] \* k\[2\] \* … \* k\[m\] 可能的最大乘积是多少？  
例如，当绳子的长度为8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

## 思路 ##

1.使用动态规划求解，当长度为n时，设最大乘积为f(n) = max(f(i) \* f(n-i))，自下向上求解并把f(n)保存在数组中  
时间复杂度为O(n²)，空间复杂度为O(n)  
2.使用贪婪算法求解  
当 n>=5时，  
a. 2(n-2) > n  
b. 3(n-3) > n  
c. 3(n-3) >= 2(n-2)  
由ab可得，绳子长度减成长度为2、3的小绳子肯定比不剪来的好。由c可得，当n>=5时，剪成3的比剪成2的好。  
当长度为4时，应该剪成2+2

## 代码 ##

/**
     * 动态规划解决
     * 时间O(n²)，空间O(n)
     * f(n) = max(f(i), f(n-i))
     */
    public static int cuttingRopeInDynamic(int length) {
        if(length < 2)
            return 0;
        if(length == 2)
            return 1;
        if(length == 3) 
            return 2;
    
        int[] max = new int[length+1];
        max[0] = 0;
        max[1] = 1;
        max[2] = 2;
        max[3] = 3;
    
        for(int i = 4; i <= length; ++i) {
            int maxValue = 0;
            for(int j = 1; j <= i / 2; ++j) {
                int tmp = max[j] * max[i - j];
                if(tmp > maxValue)
                    maxValue = tmp;
            }
            max[i] = maxValue;
        }
        return max[length];
    }
    
    /**
     * 贪婪算法解决
     * 当 n >= 5 时，
     * 2(n-2) > n
     * 3(n-3) > n
     * 3(n-3) >= 2(n-2)
     * 
     * 时间O(1)，空间O(1)
     */
    public static int cuttingRopeInGreedy(int length) {
        if(length < 2)
            return 0;
        if(length == 2)
            return 1;
        if(length == 3) 
            return 2;
    
        int timesOf3 = length / 3;
    
        // 尽可能多的剪去长度为3的绳子
        length -= timesOf3 * 3;
    
        // 如果绳子最后剩下长度为4，应该剪成 2+2，而不是 3+1
        if(length == 1) {
            timesOf3 -= 1;
            return (int) Math.pow(3, timesOf3) * 2 * 2;
        }
        else if(length == 0) {
            return (int) Math.pow(3, timesOf3);
        }
        // length == 2
        else {
            return (int) Math.pow(3, timesOf3) * 2;
        }
    }

## 测试 ##

public static void main(String[] args) {
        test1();
        test2();
    }
    
    private static void test1() {
        for(int i = -1; i < 10; ++i) {
            System.out.print(_14_CuttingRope.cuttingRopeInDynamic(i) + " ");
        }
        System.out.println();
    }
    
    private static void test2() {
        for(int i = -1; i < 10; ++i) {
            System.out.print(_14_CuttingRope.cuttingRopeInGreedy(i) + " ");
        }
        System.out.println();
    }

[Link 1]: https://github.com/linpeiyou/CodingInterviews