题⽬描述
给你⼀根⻓度为 n 的绳⼦，请把绳⼦剪成整数⻓的 m 段（ m 、 n 都是整数， n > 1 并且 m >
1 ， m <= n ），每段绳⼦的⻓度记为 k[1] ,..., k[m] 。请问 k[1] * k[2] * ... * k[m] 可能的最⼤乘积是多少？例如，当绳⼦的⻓度是 8 时，我们把它剪成⻓度分别为 2 、3 、3 的三段，此时得到的最⼤乘积是 18 。
由于答案过⼤，请对 998244353 取模。
思路解答
动态规划
这道题其实如果不是数值很⼤，可以直接使⽤动态规划来完成：
每个⻓度的绳⼦，要么最⻓的情况是不剪开（⻓度是本身），要么⻓度是剪开两段的乘积。因此每个⻓度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];
}
}但是由于数值⽐较⼤，直接乘积的时候就溢出了
找规律
我们仔细观察就会发现：要想乘积⽐较⼤，在没有1的前提下，优先使⽤3，如果出现1，那么优先使⽤2
⽐如：
2 = 1 + 1
3 = 1 + 2
4 = 2 + 2
5 = 2 + 3
6 = 3 + 3
7 = 3 + 2 + 2
8 = 3 + 3 + 2
9 = 3 + 3 + 3
10 = 3 + 3 + 2 + 2
11 = 3 + 3 + 3 + 2
12 = 3 + 3 + 3 + 3public class Solution {
public long cutRope(long number) {
if (number == 2) return 1;
if (number == 3) return 2;
long res = 1;
while (number > 4) {
res *= 3;
res = res % 998244353;
number -= 3;
}
return res * number % 998244353;
}
}结果很不幸：运⾏超时:您的程序未能在规定时间内运⾏结束，请检查是否循环有错或算法复杂度过⼤。
于是我们需要想到其他的⽅式，如何快速计算 3 的 n 次⽅，这是我们需要解决的问题，因为在尽量凑 3的前提下，有以下三种情况：
- 被 3 整除 等于 n ：直接计算 3 的 n 次幂
- 被 3 取余数为1，结果等于 n ：直接计算 3 的 （n-1） 次幂，再乘以4，为什么呢？因为余数是1，我们避免有1，需要借出 3，和 1凑成为 4，4 分段之后的最⼤乘积也是 4（2 * 2）
- 被 3 取余数为 2，结果等于 n：直接计算 3 的 n 次幂 ，再乘以2
在计算幂次⽅的时候，为了避免溢出，在每次相乘的时候，都需要除以998244353 ,为了计算快，每次以⾃身相乘的⽅式计算，代码如下：
public class Solution83 {
//计算a^n次⽅的结果
long pow(long a, long n) {
long ans = 1;
while (n > 0) {
if (n % 2 == 1) ans = (ans * a) % 998244353;
a = (a * a) % 998244353;
// ⾃身乘以⾃身，快速计算
n /= 2;
}
return ans;
}
public long cutRope(long number) {
if (number == 2) return 1;
if (number == 3) return 2;
if (number % 3 == 0) {
return pow(3, number / 3);
} else if (number % 3 == 1) {
return 4 * pow(3, (number - 4) / 3) % 998244353;
} else {
return (2 * pow(3, (number - 2) / 3)) % 998244353;
}
}
}