和剪绳子1相同的题：
思路：利用动态规划:
因为每个长度大于3的绳子的最大值都可以划分为2和3的乘积
我们想将长度为 2 3的绳子的最大值先算出来
然后再利用动态规划，进步算出长度为n的绳子的最大值
class Solution {
/*
思路：利用动态规划
因为每个长度大于3的绳子的最大值都可以划分为2和3的乘积
我们想将长度为 2 3的绳子的最大值先算出来
然后再利用动态规划，进步算出长度为n的绳子的最大值
*/
public int cuttingRope(int n) {
//长度为2时的最大值
if(n==2)return 1;
//长度为3的时候的最大值
if(n==3)return 2;
//创建动态规划数组
int[] dp=new int[n+1];
//因为最大值一定是2 3的组合，所以，我们将dp[2]和dp[3]赋值为2 3
dp[2]=2;
dp[3]=3;
//进行动态规划
for(int i=4;i<=n;i++){
for(int j=1;j<=i/2;j++){
dp[i]=Math.max(dp[j]*dp[i-j],dp[i]);
}
}
return dp[n];
}
}
评论区的一位大神的贪心解法：
b站up的视频讲解链接：【剑指offer 14- II. 剪绳子 II-哔哩哔哩】 https://b23.tv/gp3OtKN（讲的很清晰，是剪绳子ii的，方法原理一致）
class Solution {
/*
利用的是一种贪心的求法：
因为规律可以知道，绳子的最大值可以被分解为2和3的乘积，而乘积中3越多，乘积越大，越接近我们要的最大值。
所以我们的思路就是乘尽可能多的3.
*/
public int cuttingRope(int n) {
//排除几个情况（剩余绳子的长度）
if(n == 2)
return 1;
if(n == 3)
return 2;
int res = 1;
//开始剪绳子
while(n > 4){
//不断把当前的绳子剪3
res *= 3;
n -= 3;
}
//返回（最后剩下的一定是小于等于4的长度，所以直接乘上去就行）
return res * n;
}
}
这题相比于上一个题，就是多了大数处理，因为max函数无法操作取余后的数，所以我们要对上一道题的动态规划解法做一点处理，同时对贪心解法，进行一点大数取余改进。
动态规划：
import java.math.BigInteger;
class Solution {
public int cuttingRope(int n) {
//使用BigInteger
BigInteger dp[] = new BigInteger[n + 1];
//将数组里每一个变量都填充为1
Arrays.fill(dp, BigInteger.valueOf(1));
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i] = dp[i].max(BigInteger.valueOf(j * (i - j))).max(dp[i - j].multiply(BigInteger.valueOf(j)));
}
}
return dp[n].mod(BigInteger.valueOf(1000000007)).intValue();
}
}
贪心解法：
class Solution {
public int cuttingRope(int n) {
if(n == 2)
return 1;
if(n == 3)
return 2;
//改进1:因为int不满足范围，我们要使用long
long res = 1;
while(n > 4){
res *= 3;
//这里要每一步进行取余
res = res % 1000000007;
n -= 3;
}
//结果强制转换为int，同别忘取余
return (int)(res * n % 1000000007);
}
}