给你一根长度为n的绳子，请把绳子剪成整数长的 m 段（m、n 都是整数，n>1 并且 m>1，m<=n），每段绳子的长度记为 k[1],...,k[m]。请问 k[1]x...xk[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18
解题思路
使用动态规划来解决这道题目。考虑一点：如果分段数为 target，那么必然有一个点，把 target 分成两段，两段分别构成最小子问题。而这两段的最大值的乘积，也就是 target 所求的最大值。
设划分点为 i，f[i] 表示长度为 i 的绳子的乘积最大值。可得转移方程：f[i] = MAX{f[j]*f[i-j]}，其中 0 < j < i
public class Solution {
public int cutRope(int target) {
int[] f = new int[target + 1];
// 初始化
f[0] = 0;
f[1] = 1;
for (int i = 1; i <= target; i++) {
/**
* 处理不分割的情况，假设有f[6]
* 那么f[6]的最大乘积是3*3=9，那么f[3]就不能被分割了
* 如果f[i] = i，证明最大就是它本身
* 除非到了target，否则不能分割
* 至于i==target将f[i]=1，是防止target本身就是最大
*/
if(i==target) {
f[i] = 1;
}else {
f[i] = i;
}
for (int j = 1; j < i; j++) {
f[i] = Math.max(f[i],f[j]*f[i-j]);
}
}
return f[target];
}
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
