(java)剪绳子:给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n＞1并且m＞1，m＜=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最

题目描述

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

分析：

target=2, 最优解：1 1
target=3, 最优解：2 1
target=4, 最优解：2 2
target=5, 最优解：3 2
target=6, 最优解：3 3
target=7, 最优解：3 2 2
target=8, 最优解：3 3 2
target=9, 最优解：3 3 3
target=10,最优解：3 3 2 2
target=11,最优解：3 3 3 2
target=12,最优解：3 3 3 3
target=13,最优解：3 3 3 2 2
target=14,最优解：3 3 3 3 2
target=15,最优解：3 3 3 3 3
不难看出，当target>4时，应把绳子剪成尽量多的3，让剩下的都是2这样的组合。

代码

public class Solution {
    public int cutRope(int target) {
        double result = 0;
        if(target==2){
            return 1;
        }
        else if (target==3){
            return 2;
        }
        else if (target==4){
            return 4;
        }
        else {
            for (int i = 0; i <= target/3; i++) {
                for (int j = 0; j < target/2; j++) {
                    if ((3*i+j*2)==target){
                        result = Math.pow(3,i)*Math.pow(2,j);
                    }
                }

            }
        }
        return (int)result;
    }
}

这里我的代码时间复杂度O（n*n）太高了，感觉不太行

大神解法

摘自
动态规划：动态规划，先自上而下分析，在长度为n的绳子所求为f(n)，剪下一刀后剩下的两段长度是i和n-i，在这个上面还可能继续减(子问题)，所以：
f(n)=max(f(i)×f(n−i))

然后自下而上的解决问题，可以从f(1)开始向上计算并打表保存，最终获得f(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;//到3为止都是不剪最好

        int max = 0;//用于记录最大乘积
        //对于4以上的情况,每次循环要求f(i)
        for (int i = 4; i <= target ; i++) {
            max = 0;//每次将最大乘积清空
            //因为要计算f(j)乘以f(i-j)的最大值,j超过i的一半时是重复计算
            //所以只需要考虑j不超过i的一半的情况 
            for (int j = 1; j <= i/2 ; j++) {
                int product = products[j] * products[i-j];
                if (product >max){
                     max = product;
                }
            }
            products[i] = max;
        }
        max = products[target];
        return max;
    }
}