题目描述
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
与主站 整数拆分 一致
动态规划：
-
对于正整数n，当n>=2时，可以拆分成至少两个正整数和。
-
令k是拆分出的第一个正整数，则剩下的部分是n-k，n-k可以不继续拆分，也可以继续拆分成至少两个正整数的和。
-
每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积。（动态规划）
-
创建数组dp[n+1]，其中dp[i]表示将正整数拆分成至少两个正整数的和之后，这些正整数的最大乘积。特别地，0和1不可以拆分，所以dp[0]=dp[1]=0
-
当正整数i>=2时： 将i拆分成j和i-j的和，如果i-j不再拆分，则乘积为j*（i-j）；如果i-j继续拆分，则乘积为j*dp[i-j]
-
因此，当j固定时，dp[i] = max(j*（i-j),j*dp[i-j])
代码：
class Solution {
public int cuttingRope(int n) {
int dp[] = new int[n+1];
for(int i = 2;i<=n;i++){
int curmax = 0;
for(int j = 1;j<i;j++){
curmax = Math.max(curmax,Math.max(j*(i-j),j*dp[i-j]));
}
dp[i] = curmax;
}
return dp[n];
}
}
本文地址：https://blog.csdn.net/stonney/article/details/109637819
