剑指Offer | 剪绳子（进阶版）
Part0前言
剑指Offer & LeetCode刷题仓库：
https://github.com/Damaer/CodeSolution文档地址：https://damaer.github.io/CodeSolution/刷题仓库介绍：刷题仓库：CodeSolution编程知识库：https://github.com/Damaer/Coding文档地址：https://damaer.github.io/Coding/#/剑指OfferV1 系列已经完成，补增 V2 题目以及C++语言解法，欢迎关注~了解数据结构可以点击：万字长文带你漫游数据结构世界
Part183. 剪绳子（进阶版）
1题目描述
给你一根长度为 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 取模。
2思路 & 解答
这道题其实如果不是数值很大，我们可以使用动态规划来完成：
每个长度的绳子，要么最长的情况是不剪开（长度是本身），要么长度是剪开两段的乘积。因此每个长度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];
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 + 3
实现代码如下：
public 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;
}
}
}
C++ 代码如下：
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param number long长整型
* @return long长整型
*/
long long cutRope(long 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;
}
}
//计算a^n次方的结果
long long pow(long a, long n) {
long long ans = 1;
while (n > 0) {
if (n % 2 == 1) ans = (ans * a) % 998244353;
a = (a * a) % 998244353;
// 自身乘以自身，快速计算
n /= 2;
}
return ans;
}
};
【作者简介】
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人网站：http://aphysia.cn ,关注我，我们一起成长吧~
腾讯云开发者
