給定一個正整數?n?，將其拆分為 k 個 正整數 的和（?k >= 2?），并使這些整數的乘積最大化。返回 你可以獲得的最大乘積?。示例 1:輸入: n = 2 輸出: 1 解釋: 2 = 1 + 1, 1 × 1 = 1。 示例?2:輸入: n = 10 輸出: 36 解釋: 10 = 3 + 3 + 4, 3 ×?3 ×?4 = 36。

步驟一、確定狀態:

確定dp數組及初始化含義 dp[i]:分拆數字i，可以得到的最大乘積為dp[i]。

步驟二、推斷狀態方程:

1.j×(i?j)可以得到一個i的乘積， 這個是每個數拆分成2個正整數相加的情況的乘積 2. j×dp[i?j]
3. dp[i]
4.從當前j這里獲得的最大乘積為:max(j×(i?j),j×dp[i?j]) 而當前i處獲得的最大乘積: dp[i]=max(max(j×(i?j),j×dp[i?j]),dp[i])

步驟三、規定初始條件:

初始條件:
dp[0], d[1]是沒法分解的，所以從dp[2]開始，初始化為1即可

步驟四、計算順序:

這個題目需要兩層遍歷了，因為當前i的dp值，需要依賴于前面的所有dp值。 i從3到n遍歷

j從1到i?1遍歷

class Solution:def integerBreak(self, n: int) -> int:dp = [0] * (n+1)dp[2] = 1for i in range(3, n+1):for j in range(1, i):dp[i] = max(max(j*(i-j),j*dp[i-j]), dp[i])return dp[n]

總結

以上是生活随笔為你收集整理的87. Leetcode 343. 整数拆分 (动态规划-基础题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。