image.png
这里用到的是动态规划
原长度是i，然后去看i-j和j是否需要拆分，分别来比较拆分和不拆分对结果的影响，讨论这四种情况
其中，根据i-j和j是否能拆分，分四种情况：
这里说的是否可以拆分，指的不是当长度为1，不能拆分。
如果长度是2，3可以拆分，来比较拆分和不拆分的乘积哪个大
j(i-j)代表都为1，不能再拆了
dp[j](i-j)) j可以拆分，i-j不可拆分
我们来比较：j(i-j),dp[j](i-j)),dp[i-j]j,dp[i-j]dp[j]这四个哪个比较大
以此类推
image.png
得出动态规划的状态转移方程为：
dp[i]=Math.max(dp[i],Math.max(dp[j],j)*Math.max(i-j,dp[i-j]));
class Solution {
public int cuttingRope(int n) {
int [] dp=new int[n+1];
dp[1]=1;//不可拆分
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){//这里的n大于1，表示必须要拆分
int temp=Math.max(Math.max(j*(i-j),dp[j]*(i-j)),Math.max(dp[i-j]*j,dp[i-j]*dp[j]));
dp[i]=Math.max(dp[i],temp); }
}
return dp[n];
}
}
网友评论