動態(tài)規(guī)劃入門

動態(tài)規(guī)劃(Dynamic programming, 簡稱DP), 通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。

DP常常適用于有重疊子問題和最優(yōu)子結構性質的問題,動態(tài)規(guī)劃方法所消耗的時間往往遠小于樸素解法。

1. 基本思想與策略

基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。

由于動態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個特點，為減少重復計算，對每一個子問題只解一次，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中。

一言以蔽之：大事化小，小事化了。

分治與動態(tài)規(guī)劃

共同點：兩者都要求原問題具有最優(yōu)子結構性質，都是將原問題分而治之，分解成若干個規(guī)模較小的子問題，然后將子問題的解合并，最終得到答案。

不同點：分治法將分解后的子問題看成相互獨立的，通常用遞歸來做。動態(tài)規(guī)劃將分解后的子問題理解為相互間有聯(lián)系，有重疊部分，需要記憶，通常用迭代來做。

2. 使用的情況

能采用動態(tài)規(guī)劃求解的問題通常要具備３個性質：

最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結構，即滿足最優(yōu)化原理
無后效性：即某階段狀態(tài)一旦確定，就不受這個狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當前狀態(tài)有關。
有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質并不是動態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢）

3. 求解的基本步驟

動態(tài)規(guī)劃的設計都有一定的模式，一般要經(jīng)歷一下幾個步驟。

初始狀態(tài)-->|決策１|-->|決策２|-->...-->|決策Ｎ|-->結束狀態(tài)

劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。
確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當然，狀態(tài)的選擇要滿足無后效性。
確定決策并寫出狀態(tài)轉移方程：因為決策和狀態(tài)轉移有著天然的聯(lián)系，狀態(tài)轉移就是根據(jù)上一階段的狀態(tài)和決策來導出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉移方程也就可寫出。但事實上常常是反過來做，根據(jù)相鄰兩個階段的狀態(tài)之間的關系來確定決策方法和狀態(tài)轉移方程。
尋找邊界條件：給出的狀態(tài)轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。

一般，只要解決問題的階段、狀態(tài)和狀態(tài)轉移決策確定了，就可以寫出狀態(tài)轉移方程（包括邊界條件）。

實際應用中可以按以下幾個簡化的步驟進行設計：

（1）分析最優(yōu)解的性質，并刻畫其結構特征。

（2）遞歸的定義最優(yōu)解。

（3）以自底向上或自頂向下的記憶化方式（備忘錄法）計算出最優(yōu)值

（4）根據(jù)計算最優(yōu)值時得到的信息，構造問題的最優(yōu)解

參考流程：

遞歸的暴力解法 -> 帶備忘錄的遞歸解法 -> 非遞歸的動態(tài)規(guī)劃解法

4. 舉例

例１：斐波那契數(shù)列

暴力的遞歸算法

時間復雜度:O(2^n)

class Solution:
    def fib(self, N: int):
        if N <= 1:
            return N
        return self.fib(N-1) + self.fib(N-2)

遞歸樹

觀察遞歸樹，很明顯發(fā)現(xiàn)算法低效的原因：存在大量重復計算，如Ｆ(18）被計算了兩遍。

帶備忘錄的遞歸算法

class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        self.cache = {0: 0, 1: 1}
        return self.memoize(N)

    def memoize(self, N: int) -> {}:
        if N in self.cache.keys():
            return self.cache[N]
        self.cache[N] = self.memoize(N-1) + self.memoize(N-2)
        return self.memoize(N)

帶備忘錄

動態(tài)規(guī)劃的遞歸算法

class Solution2:  # 動態(tài)規(guī)劃
    def fib(self, N: int) -> int:
        if N == 0:
            return 0
        a, b = 0, 1
        for _ in range(2, N+1):
            a, b = b, a+b
        return b

動態(tài)轉移方程

斐波那契數(shù)的動態(tài)轉移方程

DP問題最困難的就是寫出狀態(tài)轉移方程，即這個暴力解。優(yōu)化方法無非是用備忘錄或者 DP table，再無奧妙可言。

例2：湊零錢問題

給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數(shù)來計算可以湊成總金額所需的最少的硬幣個數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回 -1。

示例 1:

輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例 2:

輸入: coins = [2], amount = 3
輸出: -1

說明:
你可以認為每種硬幣的數(shù)量是無限的。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/coin-change

狀態(tài)轉移方程

遞歸方法

根據(jù)狀態(tài)轉移方程寫代碼：

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if amount == 0:
            return 0
        ans = float('inf')
        for coin in coins:
            # 金額不可達
            if amount - coin < 0:
                continue
            subProb = self.coinChange(coins, amount - coin)
            # 子問題無解
            if subProb == -1:
                continue
            ans = min(ans, subProb + 1)
        return ans if ans != float('inf') else -1

帶備忘錄的遞歸算法

class Solution3(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        memo = {0: 0}

        def helper(n):
            if n in memo:
                return memo[n]
            res = float("inf")
            for coin in coins:
                if n >= coin:
                    res = min(res, helper(n - coin) + 1)
            memo[n] = res
            return res

        return helper(amount) if (helper(amount) != float("inf")) else -1

動態(tài)規(guī)劃

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        dp=[float("inf")]*(amount+1)
        dp[0]=0
        for i in range(1,amount+1):
            for coin in coins:
                if(i>=coin):
                    dp[i]=min(dp[i],dp[i-coin]+1)
        return dp[-1] if(dp[-1]!=float("inf")) else -1

5. LeetCode

64. 最小路徑和

題目描述

給定一個包含非負整數(shù)的 m x n 網(wǎng)格，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。

說明：每次只能向下或者向右移動一步。

示例:

輸入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因為路徑 1→3→1→1→1 的總和最小。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-path-sum

解題思路

二維動態(tài)規(guī)劃:

分情況：

空矩陣
只有1行
只有1列
左邊和上邊都是矩陣邊界

不需要建立DP矩陣，直接遍歷grid[i][j]修改即可

最短路徑和

代碼實現(xiàn)

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        for i in range(len(grid)):  # 共i行
            for j in range(len(grid[0])):  # 共j列
                if i == j == 0:
                    continue
                elif i == 0:
                    grid[i][j] = grid[i][j-1] + grid[i][j]
                elif j == 0:
                    grid[i][j] = grid[i-1][j] + grid[i][j]
                else:
                    grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
        return grid[-1][-1]

70. 爬樓梯

題目描述

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數(shù)。

示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。

1.  1 階 + 1 階
2.  2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。

1.  1 階 + 1 階 + 1 階
2.  1 階 + 2 階
3.  2 階 + 1 階
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/climbing-stairs

解題思路

一維動態(tài)規(guī)劃

易得DP數(shù)組公式：

dp[i] =dp[i-1]+dp[i-2]

DP數(shù)組也可以省略

爬樓梯

代碼實現(xiàn)

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            return 0
        res,last = 1,1
        for _ in range(1,n):
            res,last = res+last,res
        return res

121. 買賣股票的最佳時機

題目描述

給定一個數(shù)組，它的第 i 個元素是一支給定股票第 i 天的價格。

如果你最多只允許完成一筆交易（即買入和賣出一支股票），設計一個算法來計算你所能獲取的最大利潤。

注意你不能在買入股票前賣出股票。

示例 1:

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

示例 2:

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

解題思路

變量buying_price記錄買入價，一旦遇到更低的買入價則更新此變量，使用max_profit記錄可獲得的最大收益，當收益更高是更新max_profit

代碼實現(xiàn)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        max_profits = 0
        buying_price = prices[0]
        for i in range(len(prices)):
            if prices[i]<buying_price:
                buying_price = prices[i]
            else:
                profit = prices[i] - buying_price
                if profit>max_profits:
                    max_profits = profit
        return max_profits

198. 打家劫舍

題目描述

你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。

給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。

示例 1:

輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。

示例 2:

輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。
偷竊到的最高金額 = 2 + 9 + 1 = 12 。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/house-robber

解題思路

動態(tài)規(guī)劃方程：

dp[n] = MAX( dp[n-1], dp[n-2] + num )

由于不可以在相鄰的房屋闖入，所以在當前位置 n 房屋可盜竊的最大值，要么就是 n-1 房屋可盜竊的最大值，要么就是 n-2 房屋可盜竊的最大值加上當前房屋的值，二者之間取最大值

代碼實現(xiàn)

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0
        dp = [0] * (n + 1)
        dp[1] = nums[0]
        for i in  range(2,n + 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
        return dp[-1]

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

動態(tài)規(guī)劃入門