14 剪绳子

leetcode-cn

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

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

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

动态规划

如果长度为 2 最佳答案为 1，如果长度为 3 最佳答案为 2，如果长度为 4 最佳答案为 4，如果长度为 5 最佳答案为 6，分解为，如果长度为 6 最佳答案为 9，如果长度为 7 最佳答案为 12。

如果可以不剪，长度为 2 时最佳结果为 2，长度为 3 时最佳结果为 3，长度为 4 时最佳结果为 4，可以拆开成 1 和 3 或 2 和 2 的子问题。以此类推。f(a+b) = Max ( f(a) * f(b) )

f(2) = 2
f(3) = 3
f(4) = Max( f(2)*f(2) , f(1)*f(3) ) = 4
f(5) = Max( f(2)*f(3) , f(1)*f(4) ) = 6
...

可以使用动态规划根据前面的结果一直求到 n 的结果

public class Solution {
    public int cutRope(int target) {
        if(target<2) return 0;
        if(target==2) return 1;
        if(target==3) return 2;
        
        int[] products=new int[target+1];
        products[0]=0;
        products[1]=1;
        products[2]=2;
        products[3]=3;
        
        for(int i=4;i<=target;++i){
            int max=0;
            for(int j=1;j<=i/2;++j){
                max=Math.max(max, products[j]*products[i-j]);
            }
            products[i]=max;
        }
        return products[target];
    }
}

贪心算法

除了 4 的情况剪为 2 和 2 的两段最优，其它情况尽可能建成长度 3 最优，因此尽可能多剪成长度为 3 的段。

public class Solution {
    public int cutRope(int target) {
        if(target<2) return 0;
        if(target==2) return 1;
        if(target==3) return 2;
        
        int n = target/3;
        if(target%3 == 1){
            --n;
        }
        int remain = target-3*n==0?1:target-3*n;
        return ((int)Math.pow(3, n))*remain;
    }
}