1. DP 求解

假设 res[n] 代表长度为 n 的绳子的最大乘积，那么 res[n] = max(res[n-i] * res[i])，其中(1<=i<n)

特别的有一些特殊值：

​ res[0] = 0; //不存在

​ res[1] = 1;

​ res[2] = 2; //在长度为2时该绳子就不应该被分割了，分割会更小

​ res[3] = 3; //在长度为3时不应该被分割，分割会更小

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
	public int cuttingRope(int n) {
		if(n==2)
			return 1;
		if(n==3)
			return 2;
		// res 数组代表长度为i 的绳子的最大乘积
		// 注意res[2]此时为2不为1，因为绳子长度此时大于3，那么如果划分到了长度为2的一段就不应该被切割，保持原绳子长度即可
		int []res = new int[n+1];
		res[0]=0;
		res[1]=1;
		res[2]=2;
		res[3]=3;
		for(int i=4;i<=n;i++) {
			int tempMax = 0;
			for(int j=1;j<=i/2;j++) {
				tempMax = Math.max(tempMax,res[j]*res[i-j]);
			}
			res[i] = tempMax;
		}
		return res[n];
	}
}

2. 贪心法

可以通过数学方法证明如下推论：

  • 推论一：合理的切分方案可以带来更大的乘积

设一根绳子长度为n（n>1），切分为两段 n = n1+n2，切分为三段 n = n1+n2+n3。根据经验推测，三段的乘积往往更大，即往往有 n1n2n3 > n1n2。

当然也存在反例，比如两段 6 =3+3 和三段 6 =2+2+2，则有 3×3 > 2×2×2

  • 推论二：若切分方案合理，绳子切分越多，乘积越大

总体上看，貌似长绳子切分为越多，但其实到某个长度分界点后，乘积到达最大值就不再切分了。

  • 推论三：为使乘积最大，只有长度为2和3的绳子不应再切分，切3比2更优

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
	public int cuttingRope(int n) {
		if(n==2)
			return 1;
		if(n==3)
			return 2;
		int count = Math.floor(n/3);   //计算能够划分为长度为3的绳子段数
		int left = n%3;   //计算余数
		if(left == 0) return Math.pow(3,count);     //长度是3的整倍数
		else if(left == 1) return Math.pow(3,count-1)*4;  //长度按3划分后还剩余一段1
		else return Math.pow(3,count)*2;    //长度按3划分后还剩余一段2
	}
}

1.DP的缺陷(不可用)

这个题和剪绳子I一样的描述，就是数据范围变大了。剪绳子可以用动态规划或者贪心做，这道题对于使用DP难度就增大了一些，因为数据范围变得比较大时，long已经不足以去存储中间结果的状态，但是由于DP做法是枚举各种剪的情况然后取最大值，因此只能通过使用BigInteger的方法去做，这点评论区已经有人给出了解答。

那么这个题范围变大的本意是想让我们使用贪心算法能更好的求解(毕竟BigInteger使用起来麻烦，贪心没有数据溢出的问题，它是找当下的最优解，不需要比较，中间结果可以直接取模)。

2. 贪心法(可用)

我们首先考虑对于一段长n的绳子，我们可以切出的结果包含什么？

1 会包含吗？ 不会，因为1 * (k - 1) < k, 只要把1和任何一个其他的片段组合在一起就有个更大的值
2 可以
3 可以
4 可以吗？ 它拆成两个2的效果和本身一样，因此也不考虑
5 以上可以吗？ 不可以，这些绳子必须拆，因为总有一种拆法比不拆更优，比如拆成 k / 2 和 k - k / 2

综上, 最后的结果只包含2和3(当然当总长度为2和3时单独处理), 那么很显然n >= 5时， 3*(n - 3) >= 2 * (n - 2) ，因此我们优先拆成3，最后剩余的拆成2。最后的结果一定是由若干个3和1或2个2组成.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int cuttingRope(int n) {
        if(n == 2) {
            return 1;
        }
        if(n == 3){
            return 2;
        }
        int mod = (int)1e9 + 7;
        long res = 1;
        while(n > 4) {
            res *= 3;
            res %= mod;
            n -= 3;
        }
        return (int)(res * n % mod);
    }
}

3.快速幂解(基于贪心法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
private int mod = (int)1e9 + 7;

public int cuttingRope(int n) {
    if(n < 4){
        return n-1;
    }
    int cnt3 = n / 3;
    if(n % 3 == 0){
        return (int)pow(3, cnt3);
    } else if(n % 3 == 1){
        return (int)((pow(3, cnt3 - 1) * 4) % mod);
    } else {
        return (int)((pow(3, cnt3) * 2) % mod);
    }
}

private long pow(long base, int num){
    long res = 1;
    while(num > 0){
        if((num & 1) == 1){
            res *= base;
            res %= mod;
        }
        base *= base;
        base %= mod;
        num >>= ;
    }
    return res;}
}

快速幂算法：https://blog.csdn.net/qq_19782019/article/details/85621386