【每日一题】剑指 Offer 14- I. 剪绳子

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

示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：2 <= n <= 58

贪心算法

设一绳子长度为 n ( n>1 )，则其必可被切分为两段 n=n_1+n_2,
根据经验推测，切分的两数字乘积往往原数字更大，即往往有 n_1 * n_2 > n_1 + n_2 = n

• 例如绳子长度为 6 ：6=3+3<3×3=9 ；
• 也有少数反例，例如 2 ：2=1+1>1×1=1 。
  推论一： 合理的切分方案可以带来更大的乘积。

设一绳子长度为 n( n>1n>1 )，切分为两段 n=n_1+n_2 ，切分为三段 n=n_1+n_2+n_3 。
根据经验推测，三段 的乘积往往更大，即往往有 n_1* n_2* n_3 > n_1* n_2

• 例如绳子长度为 9： 两段 9=4+5 和 三段 9=3+3+3，则有 4×5<3×3×3 。
• 也有少数反例，例如 66 ： 两段 6=3+3和 三段 6=2+2+2，则有 3×3>2×2×2 。
  推论二： 若切分方案合理，绳子段切分的越多，乘积越大。

总体上看，貌似长绳子切分为越多段乘积越大，但其实到某个长度分界点后，乘积到达最大值，就不应再切分了。
问题转化： 是否有优先级最高的长度 xx 存在？若有，则应该尽可能把绳子以 xx 长度切为多段，以获取最大乘积。
推论三： 为使乘积最大，只有长度为 2 和 3 的绳子不应再切分，且 33 比 22 更优 （详情见下表） 。

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        if(b == 0) return (int)Math.pow(3, a);
        if(b == 1) return (int)Math.pow(3, a - 1) * 4;
        return (int)Math.pow(3, a) * 2;
    }
}

复杂度分析：
时间复杂度 O(1) ： 仅有求整、求余、次方运算。
求整和求余运算：资料提到不超过机器数的整数可以看作是 O(1) ；
幂运算：查阅资料，提到浮点取幂为 O(1) 。
空间复杂度 O(1) ： 变量 a 和 b 使用常数大小额外空间。

找规律

思路
首先把题目抽丝剥茧，题目套了个剪绳子的壳子。其实就是数字n，如何分解保证乘积最大。不妨举几个例子：

• 第一步：定义dp[n]的值的含义为：数字n的乘积最大值

n=2:  1+1  -->1*1=1;   				dp[2]=1;
n=3:  2+1  -->2*1=2;   				dp[3]=2;
n=4:  2+2  -->2*2=4;   				dp[4]=4;
n=5:  3+2  -->3*2=6;   				dp[5]=6;
貌似看不出规律，别急再多写几个
n=6:  3+3  -->3*3=4;                 dp[6]=9;
n=7:  4+3  -->4*3=12;-->dp[4]*3=12   dp[7]=12;
n=8:  5+3  -->6*3=12;-->dp[5]*3=18   dp[8]=18;
n=9:  6+3  -->9*3=12;-->dp[6]*3=27   dp[9]=27;
n=10: 7+3  -->12*3=36;-->dp[7]*3=12   dp[10]=36;

• 第二步：找到递推的规律：
  通过上述分析，规律明显在n=7以后为

if(n>=7)
	dp[n] = dp[n-3]*3;

• 第三步：找初始值：
  初始值在第二步找规律已经找到了

n=2:  1+1  -->1*1=1;   				dp[2]=1;
n=3:  2+1  -->2*1=2;   				dp[3]=2;
n=4:  2+2  -->2*2=4;   				dp[4]=4;
n=5:  3+2  -->3*2=6;   				dp[5]=6;
n=6:  3+3  -->3*3=4;                dp[6]=9;

通过以上分析，就直接可以写代码了：

class Solution {
    public int cuttingRope(int n) {
        //1.创建数组-设置对应的含义,dp[n]为长度为 n 时候，最大的乘积 我们只需求出dp[n]
        int[] dp = new int[n+7];
        //3.确定初始值
        dp[0]=0;
        dp[1]=0;
        dp[2]=1;
        dp[3]=2;
        dp[4]=4;
        dp[5]=6;
        dp[6]=9;
        if(n<=6){return dp[n];}
        //2.找到递推关系
        for (int i = 7; i <= n; i++) {
            dp[i] = dp[i-3]*3;
        }
        return dp[n];
    }
}

参考文章

• 贪心算法：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/mian-shi-ti-14-i-jian-sheng-zi-tan-xin-si-xiang-by/
• 找规律：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/kan-bu-dong-suan-wo-shu-de-ti-jie-dong-tai-gui-hua/