給你一根長度為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];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/245087.html
標籤：其他