題目描述
給你一根長度為n的繩子，請把繩子剪成整數長的m段（m、n都是整數，n>1并且m>1），每段繩子的長度記為k[0],k[1],...,k[m]，請問k[0]xk[1]x...xk[m]可能的最大乘積是多少？例如，當繩子的長度是8時，我們把它剪成長度分別為2、3、3的三段，此時得到的最大乘積是18，
思路
1、動態規劃，自底向上構造dp陣列， 2、貪心法，當n>4時，3*(n-3) > 2*(n-2) > n，
代碼
貪心法
public class Solution {
public int cutRope(int target) {
if(target <= 1) {
return 0;
}
if(target == 2) {
return 1;
}
if(target == 3) {
return 2;
}
int ans = 1;
while(target > 4) {
ans *= 3;
target -= 3;
}
return target * ans;
}
}
動態規劃
public class Solution {
public int cutRope(int target) {
if(target < 2) {
return 0;
}
if(target == 2) {
return 1;
}
if(target == 3) {
return 2;
}
int[] dp = new int[target + 1];
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for(int i = 4; i <= target; i++) {
for(int j = 2; j <= i / 2; j++) {
dp[i] = Math.max(dp[i], dp[i - j] * dp[j]);
}
}
return dp[target];
}
}
筆記
無
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57197.html
標籤：其他
上一篇：機器人的運動范圍
下一篇：資料結構（C語言版）---二叉樹