【剑指14】剪绳子

一.题目描述

给你一个长度为n的绳子，请把绳子剪成m段（m，n都是整数，且都大于1）每段绳子的长度即为K[0],K[1],K[2]...K[m]。请问K[0]k[1]..k[m]可能的最大乘积是多少？

Example 2:
Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

二.分析

1.动态规划：时间复杂度为O(n2)

    public static int cut1(int length) {
        if (length < 2) return 0;
        if (length == 2) return 1;
        if (length == 3) return 2;
        int[] array = new int[length + 1];

        array[1] = 1;
        array[2] = 2;        //为什么不是上面的length==2时候的返回值1? 这里把2当作被切出一段为2的子绳子
        array[3] = 3;
        for (int i = 4; i <= length; i++) {
            int max = 0;
            for (int j = 1; j <= i / 2; j++) {
                if (array[j] * array[i - j] > max) {
                    max = array[j] * array[i - j];
                }
            }
            array[i] = max;
        }
        return array[length];
    }

2.贪心算法:时间复杂度为 O(1)

贪心算法的核心是通过局部最优解来得到全局最优解,对于分割问题来说,要使乘积最大,该问题的贪心思想是尽可能去剪为长度为3的绳子!

最优解的正确性证明：当n>=5,3(n-3)>=2(n-2);当n=4时候，剪出一个3一个1不如两个2乘积大，两个2和一个4效果一样， 为什么剩4的时候还要剪？这是考虑当若一开始时候绳子原长length==4时候，至少要剪一刀

    
    public static int cut2(int length) {
        if (length < 2) return 0;
        if (length == 2) return 1;
        if (length == 3) return 2;

        int timesOf3 = length / 3;
        int timesOf2 = 0;
        if (length % 3 == 1) {
            timesOf3--;
            timesOf2 = 2;
        } else if (length % 3 == 2) {
            timesOf2++;
        }
        return (int) Math.pow(3, timesOf3) * (int) Math.pow(2, timesOf2);
    }