leetcode(力扣) 343. 整數拆分 (動态規劃 & 數學方法)

文章目錄

• ​​題目描述​​
• ​​思路分析​​
• ​​完整代碼​​
• ​​數學​​

題目描述

給定一個正整數 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。

思路分析

先來個例子說明為啥用動态規劃，比如所給數值為n=10。

則可以拆分成 2 + 8 = 10，2無法拆分，8可以繼續拆。實際上可以發現，這裡繼續拆的話就是在找8拆分之後的乘積最大值了。也就是說，後一步依賴于前面的最優解。是以想到用動态規劃，動态規劃就是這樣，這一步依賴于前幾步的最優解，然後用那個狀态轉移方程去一步一步推到結果。

老規矩 dp五步走：

1.确定dp含義：

dp[i] 表示 整數i 的最大乘積。

2.确定遞推公式：

局部的去想這個問題，一個數 i 的拆分情況。

i 被拆分成 j 和 i-j：

i-j 可能都無法繼續拆分，那麼此時乘積就是 j * (i-j)。

i-j 可以繼續拆分，那麼實際上這裡就可以直接使用之前計算過的j的最優解 也就是 dp[i-j],此時乘積就是 j *dp[i-j]。

是以目前數值i的最大值就是上面兩種情況的一種，在加上其本身，一共三種。

​​

​dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j);​

​

3.初始化dp數組:

n= 0 和 n=1的時候都是沒法拆的，這倆都定義成0就可以了。

4.确定周遊順序：

顯然 i 是整個周遊的主指針，從 2開始周遊到我們要求的n。

然後就是要拆分的那個j，j從1周遊到i，這塊别寫錯了，假如拆10的話，最多就是1和9。

5.模拟dp數組結果

這一步我通常是省略的，先送出程式，沒通過或者輸出了再回來debug~

細節：

為什麼隻拆了i-j 不考慮拆j?

這一點其實從周遊順序裡就能看出來，第二層的for 裡 j從1周遊到了i，是以j其實是已經從1拆分到了i的，是以不需要考慮拆分他了。

完整代碼

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

數學

class Solution:
    def integerBreak(self, n: int) -> int:
        res = 1
        if n == 2:
            return 1
        if n ==3 :
            return 2
        if n == 4:
            return 4
        while n > 4:
            res *=3
            n -=3
        res *= n
        return res