動(dòng)態(tài)規(guī)劃入門
動(dòng)態(tài)規(guī)劃(Dynamic programming, 簡稱DP), 通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法。
DP常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題,動(dòng)態(tài)規(guī)劃方法所消耗的時(shí)間往往遠(yuǎn)小于樸素解法。
1. 基本思想與策略
基本思想與分治法類似，也是將待求解的問題分解為若干個(gè)子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時(shí)，列出各種可能的局部解，通過決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個(gè)子問題就是初始問題的解。
由于動(dòng)態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個(gè)特點(diǎn)，為減少重復(fù)計(jì)算，對每一個(gè)子問題只解一次，將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。
一言以蔽之：大事化小，小事化了。
分治與動(dòng)態(tài)規(guī)劃
共同點(diǎn)：兩者都要求原問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，都是將原問題分而治之，分解成若干個(gè)規(guī)模較小的子問題，然后將子問題的解合并，最終得到答案。
不同點(diǎn)：分治法將分解后的子問題看成相互獨(dú)立的，通常用遞歸來做。動(dòng)態(tài)規(guī)劃將分解后的子問題理解為相互間有聯(lián)系，有重疊部分，需要記憶，通常用迭代來做。
2. 使用的情況
能采用動(dòng)態(tài)規(guī)劃求解的問題通常要具備３個(gè)性質(zhì)：
- 最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理
- 無后效性：即某階段狀態(tài)一旦確定，就不受這個(gè)狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。
- 有重疊子問題：即子問題之間是不獨(dú)立的，一個(gè)子問題在下一階段決策中可能被多次使用到。（該性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢）
3. 求解的基本步驟
動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有一定的模式，一般要經(jīng)歷一下幾個(gè)步驟。
初始狀態(tài)-->|決策１|-->|決策２|-->...-->|決策Ｎ|-->結(jié)束狀態(tài)
劃分階段：按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。在劃分階段時(shí)，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。
確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。
確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過來做，根據(jù)相鄰兩個(gè)階段的狀態(tài)之間的關(guān)系來確定決策方法和狀態(tài)轉(zhuǎn)移方程。
-
尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。
一般，只要解決問題的階段、狀態(tài)和狀態(tài)轉(zhuǎn)移決策確定了，就可以寫出狀態(tài)轉(zhuǎn)移方程（包括邊界條件）。
實(shí)際應(yīng)用中可以按以下幾個(gè)簡化的步驟進(jìn)行設(shè)計(jì)：
（1）分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。
（2）遞歸的定義最優(yōu)解。
（3）以自底向上或自頂向下的記憶化方式（備忘錄法）計(jì)算出最優(yōu)值
（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造問題的最優(yōu)解
參考流程：
遞歸的暴力解法 -> 帶備忘錄的遞歸解法 -> 非遞歸的動(dòng)態(tài)規(guī)劃解法
4. 舉例
例１：斐波那契數(shù)列
暴力的遞歸算法
時(shí)間復(fù)雜度: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)算法低效的原因：存在大量重復(fù)計(jì)算，如Ｆ(18）被計(jì)算了兩遍。
帶備忘錄的遞歸算法
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)
動(dòng)態(tài)規(guī)劃的遞歸算法
class Solution2: # 動(dòng)態(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
動(dòng)態(tài)轉(zhuǎn)移方程
DP問題最困難的就是寫出狀態(tài)轉(zhuǎn)移方程，即這個(gè)暴力解。優(yōu)化方法無非是用備忘錄或者 DP table，再無奧妙可言。
例2：湊零錢問題
給定不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫一個(gè)函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回 -1。
示例 1:
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例 2:輸入: coins = [2], amount = 3
輸出: -1說明:
你可以認(rèn)為每種硬幣的數(shù)量是無限的。來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/coin-change
狀態(tài)轉(zhuǎn)移方程
遞歸方法
根據(jù)狀態(tài)轉(zhuǎn)移方程寫代碼：
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:
# 金額不可達(dá)
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
動(dòng)態(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. 最小路徑和
題目描述
給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。
說明：每次只能向下或者向右移動(dòng)一步。
示例:
輸入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因?yàn)槁窂?1→3→1→1→1 的總和最小。來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-path-sum
解題思路
二維動(dòng)態(tài)規(guī)劃:
分情況：
- 空矩陣
- 只有1行
- 只有1列
- 左邊和上邊都是矩陣邊界
不需要建立DP矩陣，直接遍歷grid[i][j]修改即可
代碼實(shí)現(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. 爬樓梯
題目描述
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(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
解題思路
一維動(dòng)態(tài)規(guī)劃
易得DP數(shù)組公式：
dp[i] =dp[i-1]+dp[i-2]
DP數(shù)組也可以省略
代碼實(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í)機(jī)
題目描述
給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
如果你最多只允許完成一筆交易（即買入和賣出一支股票），設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。
注意你不能在買入股票前賣出股票。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格。示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
解題思路
變量buying_price記錄買入價(jià)，一旦遇到更低的買入價(jià)則更新此變量，使用max_profit記錄可獲得的最大收益，當(dāng)收益更高是更新max_profit
代碼實(shí)現(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. 打家劫舍
題目描述
你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，能夠偷竊到的最高金額。
示例 1:
輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號(hào)房屋 (金額 = 1) ，然后偷竊 3 號(hào)房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。示例 2:
輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號(hào)房屋 (金額 = 2), 偷竊 3 號(hào)房屋 (金額 = 9)，接著偷竊 5 號(hào)房屋 (金額 = 1)。
偷竊到的最高金額 = 2 + 9 + 1 = 12 。來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/house-robber
解題思路
動(dòng)態(tài)規(guī)劃方程：
dp[n] = MAX( dp[n-1], dp[n-2] + num )
由于不可以在相鄰的房屋闖入，所以在當(dāng)前位置 n 房屋可盜竊的最大值，要么就是 n-1 房屋可盜竊的最大值，要么就是 n-2 房屋可盜竊的最大值加上當(dāng)前房屋的值，二者之間取最大值
代碼實(shí)現(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]
