剪绳子

题目描述

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

分析

​ 可以先试着找下规律,当n>=5时，总有3(n-3)>=2(n-2),而当 n=4 时,2 * 2>3 * 1。也就是说对于首先要尽可能的截为长度 3 的绳子，剩下的绳子为4时，截为2 * 2的绳子。根据这个规律，利用乘方运算就不难写出实现了。

实现

public int cutRope(int target) {
        if(target <=3){
            return target  - 1;
        }
        int x = target%3;
        int y = target/3;
        int result = 1;
        if(x == 2){
            result = 2 * (int)Math.pow(3,y);
        } else if(x == 1){
           result = 2 * 2 * (int)Math.pow(3,y-1);
        } else {
            result = (int)Math.pow(3,y);
        }
        return result;
}

当然，利用动态规划解法同样可以实现。

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