Sword to Offer-14 剪绳子 ❀❀

01 Apr 2020 in Algorithm

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

解题思路：

动态规划
1、用一个动态规划数组来储存长度为i时，可得的最大绳子切割乘积，假设j在1~i-1之间，用于切割长度为i的绳子，那么该绳子的最大乘积就是两部分的最大乘积之积的最大值;
2、注意绳长target<=3时，作为一根完整的绳子，由于必须被切割，其最大切割乘积为1,1,2,但作为更长绳子的一部分可以得到1,2,3所以要单独设置:
(1) 前三种情况题设条件得到的最优解为1,1,2;
(2) 但当它们作为绳长的一部分时，最优解是不剪切得到的1,2,3;
3、target>3，比如target=4的时候，必须剪切情况下可以得到2*2=4，不剪情况下得到的也是4，target=5的时候，必须剪切得到2*3=6，不剪切得到5；也就是说，从target=4开始往后，可以看作剪切一定能得到比不剪切更优解。

问题图解：

AC代码：

// The Range in Which the Robot Can Move

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

补充说明：

• 这里是牛客编码链接