動態規劃解法總結

總結以下剛做完的動態規劃題集，題目和彩色圖片均出自此題集，

規劃問題就是在一定約束下尋找最優解，最優解是某種價值的最大（小）化，而這種價值一定是在某種變動之中累計的，這才需要規劃，比如說青蛙跳臺階問題，一次可以跳一格，也可以跳兩格；比如說禮物的最大價值問題，每次移動可以向左也可以向右；

這種變動總是可以描述為：物體從起始位置向其他位置移動 ，價值在經過任意位置時會發生改變，且移動程序中有若干路徑可以選擇，因此解決規劃問題的關鍵就是尋找價值隨著位置改變而改變的規律，從而選擇最終價值最大的路徑，

這種規律性被總結為動態規劃的思想，我總結就是倒著想，正著解，

倒著想是指：

• 物體移動到最終位置前一步可以位于哪幾個位置？
• 移動到這幾個位置的最優解和移動到最終位置的最優解之間是否有函式關系f(x)？
• 物體從起始位置移動到哪些位置的路徑是唯一的？
• 有唯一路徑的位置的價值和從起點到其周邊位置的最優解是否也滿足函式關系f(x)?

如果二、四成立，則f(x)就是狀態轉移方程（狀態定義為到達某一位置的最優解），三則是找到了我們可以依賴的起點，從起點經過狀態轉移方程就能找打到達任意位置的最優路徑，這就是正著解，

我將我做過的動態規劃問題總結為三類，總體做法是類似的，第一題詳細講倒著想，正著解的求解思路，

第一類動態規劃問題——終點固定

1. 禮物的最大價值

在一個 m*n 的棋盤的每一格都放有一個禮物，每個禮物都有一定的價值（價值大于 0），你可以從棋盤的左上角開始拿格子里的禮物，并每次向右或者向下移動一格、直到到達棋盤的右下角，給定一個棋盤及其上面的禮物的價值，請計算你最多能拿到多少價值的禮物？

輸入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
輸出: 12
解釋: 路徑 1→3→5→2→1 可以拿到最多價值的禮物

倒著想：

• 到達最右下角前有兩步，其上方和其左側
• 最右下角的上方和左側的最優解和最終最優解的關系也很顯然，兩條路徑的價值中大者即為到達最右下角的最優解
• 到達第一行、第一列的任意位置的路徑是唯一的
• 第二條發現的規則顯然是適用于到達任意位置的

因此，這道題可以很容易寫出狀態轉移方程

有了狀態轉移方程和初始狀態，就可以正著解，也就是在第一行、第一列所有位置的最大價值已知的情況下，由狀態轉移方程依次計算出每行從左到右所有位置的最優解（這樣就能保證每個位置求解時其上、右方位置最優解已被解出），

<dir

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        row_num = len(grid)
        col_num = len(grid[0])
        for i in range(row_num):
            for j in range(col_num):
                up = grid[i - 1][j] if i != 0 else 0
                left = grid[i][j - 1] if j != 0 else 0
                grid[i][j] = max(up, left) + grid[i][j]
        return grid[row_num - 1][col_num - 1]

2. 青蛙跳臺階問題

一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階，求該青蛙跳上一個 n 級的臺階總共有多少種跳法，

答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請回傳 1，

示例 1：

輸入：n = 2
輸出：2

示例 2：

輸入：n = 7
輸出：21

示例 3：

輸入：n = 0
輸出：1

提示：

0 <= n <= 100

倒著想，很容易就寫出狀態轉移方程

倒著想，實際是一種分治思想：假設輸入n的解為F(n)，利用分治思想，思考如果低規模問題解對于原問題是否有幫助，可以發現，如果F(n-1)和F(n-2)已知，F(n) = F(n-1) + F(n - 2)，所以這是一個動態規劃問題，已經寫出狀態轉移方程
（注意：F(N-2)+1+1 和 F(n-1)+1是等價的，因為F(n-2)+1就是F(n-1)的一種跳法，這也是為什么不必考慮F(n-m)(m>1)，因為這些從F(n-m)開始的跳法最終都將到達F(n-1)或F(n-2)）

class Solution:
    def numWays(self, n: int) -> int:
        if n <= 1: return 1
        c = 2
        b = 1
        a = int(1E9 + 7)
        for i in range(n - 2):
            c, b = (c + b) % a, c
        return c

3. 把數字翻譯成字串

給定一個數字，我們按照如下規則把它翻譯為字串：0 翻譯成 “a” ，1 翻譯成 “b”，……，11 翻譯成 “l”，……，25 翻譯成 “z”，一個數字可能有多個翻譯，請編程實作一個函式，用來計算一個數字有多少種不同的翻譯方法，

輸入: 12258
輸出: 5
解釋: 12258有5種不同的翻譯，分別是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        a = b = 1
        for i in range(2, len(s) + 1):
            a, b = (a + b if "10" <= s[i - 2:i] <= "25" else a), a
        return a

4. n 個骰子的點數

把n個骰子扔在地上，所有骰子朝上一面的點數之和為s，輸入n，列印出s的所有可能的值出現的概率，

你需要用一個浮點數陣列回傳答案，其中第 i 個元素代表這 n 個骰子所能擲出的點數集合中第 i 小的那個的概率，

輸入: 2
輸出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

n個骰子總點數就有6*n種可能（其中前n種頻次為0），n個骰子總點數為y有6種路徑到達，當只有一個骰子時，到達任意點數的路徑唯一，因此可以寫出狀態轉移方程

class Solution:
    def dicesProbability(self, n: int) -> List[float]:
        dp = [1] * 6 # 存盤少一個骰子的狀態
        for i in range(2, n + 1):
            cur_num = i * 6 # 當有 i 個骰子的結果數
            cur = [0] * cur_num # 當前骰子數的狀態
            for j in range(cur_num):
                for m in range(1, 7):
                    exist = 0 <= j - m <= cur_num - 7
                    val = dp[j - m] if exist else 0
                    cur[j] += val
            dp = cur
        total = 6 ** n
        return [x / total for x in dp][n - 1:]

第二類動態規劃——終點不定

5. 連續子陣列的最大和

輸入一個整型陣列，陣列中的一個或連續多個整陣列成一個子陣列，求所有子陣列的和的最大值，

要求時間復雜度為O(n)，

輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子陣列 [4,-1,2,1] 的和最大，為 6，

這題和前面四個的差別在于，前面四個是從起點移動到固定重點的過程中某種價值累計的的最大值；而這道題中重點不是具體一個點，有幾個點就有幾個終點，最終求的是到達所有重點的價值之中最大值，

在這題中，最終解就是以任意數字結尾的最大子陣列的和中的最大值，dp[i]代表以元素 nums[i]為結尾的連續子陣列最大和
（狀態不再是不同問題規模的原問題的解，而是不同問題規模下另一個問題的解，就是包含最后元素的子陣列最大和的解，再由后者推出前者）

若dp[i?1]≤0 ，說明 dp[i - 1]對 dp[i]產生負貢獻，即 dp[i-1] + nums[i]還不如 nums[i]本身大，

因此，狀態轉移方程為 dp[i] = nums[i] + max(dp[i], 0)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] += max(nums[i - 1], 0)
        return max(nums)

最開始分情況討論，比較復雜

遇到正數就追加；更新子陣列的轉折點就是當前陣列之和加上若干負數之后和≤0，因此遇到負數也直接追加，

這樣，不管是正數和負數都直接追加，就保持了操作的統一，不需要真的去關心子陣列的范圍，只需要記錄當前子陣列的和以及出現過的最大子陣列的和就可以，這樣計算以每一個元素為結尾的最大子陣列和就能和上面的動態規劃解法一致，

第三類動態規劃

6. 買股票的最佳時機

假設把某股票的價格按照時間先后順序存盤在陣列中，請問買賣該股票一次可能獲得的最大利潤是多少？

輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 ，
     注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格，

輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0，

這題和上一題：連續子陣列的最大和，的區別在于，雖然都是重點不定，但連續子陣列的最大和問題中所有路徑通過每個點價值都會產生變化，而這題不會，這題只有起點和終點價值會變化，

這題不用考慮路徑上價值變化，回歸最樸素的想法，每天價格-之前最低價，得到每天賣的獲利，取最大即可

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_val = float('inf')
        res = 0
        for price in prices:
            min_val = min(min_val, price) # 之前天最低股價
            res = max(price - min_val, res)
        return res

住：題目和彩色圖片均出自此題集

標籤：其他

上一篇：Python采集古代精品大作，品味古典文學佳作

下一篇：哈撒給，英雄聯盟全皮膚下載器來了