- 整數拆分
給定一個正整數 n，將其拆分為至少兩個正整數的和，并使這些整數的乘積最大化， 回傳你可以獲得的最大乘積，
示例 1:
輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1，
示例 2:
輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36，
說明: 你可以假設 n 不小于 2 且不大于 58，
題解：
定義陣列dp[maxn],dp[n]表示數字n可以得到的題意描述的答案，那么設x取值范圍在[1,n-1]之間，于是我們的答案dp[n]=max(x*(n-x),xdp[n-x]);這個不難理解，x在區間[1,n-1]取值，另外的數字n-x有兩種狀態，一個是不展開，那么答案就是x(n-x)，另外一個是展開看看有沒有更大的值，于是有x*dp[n-x]，于是狀態轉移方程如上所示，
AC代碼
class Solution {
public:
int dp[60];
int integerBreak(int n) {
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
dp[i]=max(dp[i],dp[i-j]*j);
dp[i]=max(dp[i],(i-j)*j);
}
}
return dp[n];
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/237135.html
標籤：其他
上一篇：vnc連接遠端linux服務器