1. 題目

給定一個(gè)正整數(shù) n，將其拆分為至少兩個(gè)正整數(shù)的和，并使這些整數(shù)的乘積最大化。 返回你可以獲得的最大乘積。

示例 1: 輸入: 2 輸出: 1 解釋: 2 = 1 + 1, 1 × 1 = 1。示例 2: 輸入: 10 輸出: 36 解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 說(shuō)明: 你可以假設(shè) n 不小于 2 且不大于 58。

《劍指offer》同題 面試題14- I. 剪繩子

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/integer-break
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• $dp[n]$ 表示獲得的最大乘積
• 當(dāng) n+1 時(shí)，可以拆成 $(1,n),(2,n?1),(3,n?2),\dots ,(n,1)$
• $dp[n+1]=max(1?dp[n],2?dp[n?1],...,n?dp[1],...1?n,2?(n?1),...,n?1)$

class Solution { public:int integerBreak(int n) {int dp[n+1] = {0};dp[2] = 1;int i, j;for(i = 3; i <= n; ++i){for(j = 1; j <= i-2; ++j)dp[i] = max(dp[i], max(j*dp[i-j], j*(i-j)));}return dp[n];} }; class Solution { public:int cuttingRope(int n) {int dp[n+1] = {0};dp[2] = 1;int i, j;for(i = 3; i <= n; ++i){ for(j = 1; j < i; ++j)dp[i] = max(dp[i], max(j,dp[j])*max(i-j, dp[i-j]));}return dp[n];} };

n 很大的時(shí)候，避免溢出：《劍指offer》面試題14- II. 剪繩子 II

有結(jié)論：劃分成盡可能多的3，最多2個(gè)2

• 求余1，2個(gè)2
• 求余2，1個(gè)2

class Solution { public:int cuttingRope(int n) {if(n <= 3)return n-1;//盡可能多的3, 兩端最多只有2個(gè)2int p = n/3, q = n%3;long long sum = 1;if(q == 1)//多分出3個(gè)，湊成4 變成2*2 > 3*1sum *= 4, p -= 1;if(q == 2) sum *= 2;for(int i = 0; i < p; i++){sum = sum * 3 % 1000000007;}return sum;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 343. 整数拆分（DP）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。