LeetCode-面试题14-1-剪绳子

题目

给你一根长度为 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。

示例1

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

示例2

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示:

• 2 <= n <= 58

解题思路

方法1、动态规划

整体目标为最大化f(n)=max(f(i) x f(n-i))，可以看成递归自顶向下解决，但是这样会有很多重复计算。一个更好的方法是自底向上，把小的子问题最优解，然后再往上计算，子问题要存储起来，避免重复的计算过程。对于f(0)~f(3)，最优解的值是n-1，对于n>=4的数，比如4，可以切分为1，2，3的数字组合，于是dp[1]，dp[2]，dp[3]分别等于1，2，3。这里的dp[3]不等于最优解2，因为切分4并不需要对数字3再次切分。

另外一种解释是把线切的方法分为切成2段或者切成很多段，切成2段的乘积可以表示为第一段长度j，第二段长度i-j。切成多段的乘积可以表示为第一段长度为j，第二段长度为f(j-i)。到底是切2段大还是切多段大，用max函数比较一下。同时与现存的dp[i]的值比较，取最大的值。如Java代码2所示，也能够解决。

方法2、贪心算法

切的时候尽可能的使乘积最大，当n>=5时，尽可能多切长度为3的绳子；当剩下的长度为4时，切成2段长度为2的绳子，之后乘积就是切成3的次数*切成2的次数

Java代码1

class Solution {
    public int cuttingRope(int n) {
        // 此处计算f(0)~f(3)的最优解
        if(n < 4)
            return n-1;
        int[] dp = new int[n+1];
        // 当n>=4时，切分的长度有1，2，3的可能，dp[3]并不是代表f(3)的最优解
        // 因为长度为1、2、3的线是4的子集，不需要再切分
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i=4;i<=n;i++){
            for(int j=1;j<=i/2;j++){
                dp[i] = Math.max((dp[j]*dp[i-j]),dp[i]);
            }
        }
        return dp[n];
    }
}

Java代码2

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

Python代码

class Solution:
    def cuttingRope(self, n: int) -> int:
        if(n<=3): return n-1
        # 尽可能多的剪去长度为3的绳子
        count3 = n//3
        # 当绳子剩下的长度为4时，不再剪去长度为3的绳子，因为2x2>3x1，剪为3的次数减少1次
        if(n-count3*3): count3-=1
        # 重新计算差值，计算剪为2的次数
        count2 = (n-count3*3)//2
        return int(math.pow(3,count3)*math.pow(2,count2))