题目描述

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

输入描述:

输入一个数n，意义见题面。（2 <= n <= 60）

返回值描述:

输出答案。

示例1

输入

8

返回值

18

思路 & 解答

本题的解答思路就是每个长度的绳子，要么最长的情况是不剪开（长度是本身），要么长度是剪开两段的乘积。因此每个长度 length 都需要遍历两个相加之后等于 length 的乘积，取最大值。

初始化值长度为 1 的值为 1，从长度为 2 开始，每一种长度都需要遍历两个子长度的乘积。

public class Solution {
    public int cutRope(int target) {
        if (target <= 1) {
            return target;
        }
        int[] nums = new int[target + 1];
        nums[1] = 1;
        nums[0] = 1;
        for (int i = 2; i <= target; i++) {
            int max = i;
            for(int j=0;j<=i/2;j++){
                int temp = nums[j]*nums[i-j];
                if(temp>max){
                    max = temp;
                }
            }
            nums[i]=max;
        }
        return nums[target];
    }
}

C++ 代码实现如下：

class Solution {
public:
    int cutRope(int target) {
        if (target <= 1) {
            return target;
        }
        int nums[target + 1];
        for (int i = 0; i <= target; i++) {
            nums[i] = 0;
        }
        nums[1] = 1;
        nums[0] = 1;
        for (int i = 2; i <= target; i++) {
            int max = i;
            for (int j = 0; j <= i / 2; j++) {
                int temp = nums[j] * nums[i - j];
                if (temp > max) {
                    max = temp;
                }
            }
            nums[i] = max;
        }
        return nums[target];
    }
};

这道题，还可以用动态规划的思维来做，假设绳子长度为 n 的 最大的长度为 f(n)，那你说 f(n)怎么计算得来呢？

1. f(n) 可能是 n(不切分)
2. 也可能是 f(n-1) 和 f(1)的乘积
3. 也可能是 f(n-2) 和 f(2)的乘积

......

那么也就是想要求 f(n) 我们必须先把 f(n-1) ， f(n-2) ...之类的前面的值先求出来，f(1)=1 这是初始化值。

Java 代码如下:

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

C++ 代码实现如下：

class Solution {
public:
    int cutRope(int target) {
        int dp[target + 1];
        for (int i = 0; i <= target; i++) {
            dp[i] = 0;
        }
        dp[1] = 1;
        for (int i = 2; i <= target; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = max(dp[i], (max(j, dp[j])) * (max(i - j, dp[i - j])));
            }
        }
        return dp[target];
    }
};

时间复杂度：O（n²） 空间复杂度：O（n），需要创建额外的二维数组