算法套路十三——?jiǎng)討B(tài)規(guī)劃DP入門
動(dòng)態(tài)規(guī)劃和遞歸都是通過將大問題分解為較小的子問題來(lái)解決問題。它們都可以用來(lái)解決具有重疊子問題和最優(yōu)子結(jié)構(gòu)特性的問題。
- 遞歸是一種自頂向下的方法，
它從原始問題開始，遞歸地將問題分解為較小的子問題dfs(i)——dfs(i)代表的是從第i個(gè)狀態(tài)開始進(jìn)行遞歸求解能夠得到的最終結(jié)果。直到子問題可以直接解決。遞歸可能會(huì)導(dǎo)致大量的重復(fù)計(jì)算，因?yàn)樗鼪]有記錄已經(jīng)解決的子問題的解對(duì)遞歸不理解的話可以前往算法套路七——二叉樹遞歸進(jìn)行學(xué)習(xí) - 動(dòng)態(tài)規(guī)劃是一種自底向上的方法，
它從最小的子問題開始，逐步解決較大的子問題，直到解決原始問題。動(dòng)態(tài)規(guī)劃通過存儲(chǔ)已經(jīng)解決的子問題的解（通常使用表格或數(shù)組）來(lái)避免重復(fù)計(jì)算，從而提高了算法的效率。
因此，遞歸方法相對(duì)更加自然而直觀，所以在很多情況下，動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)可以從遞歸算法開始，然后通過添加記憶化（Memoizatio n）技術(shù)來(lái)優(yōu)化遞歸算法，之后對(duì)遞歸算法的代碼進(jìn)行自底向上的迭代改進(jìn)，得到動(dòng)態(tài)規(guī)劃代碼。
記憶化搜索介紹：https://oi-wiki.org/dp/memo/
算法示例：LeetCode198. 打家劫舍
你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房?jī)?nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你 不觸動(dòng)警報(bào)裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。
遞歸
首先考慮直接用遞歸解決該題，
求偷竊到的最高金額，可以按照選或不選的思路，按照以下步驟：
- ans1記錄不偷當(dāng)前房屋的最大金額即dfs(i + 1)
- ans2記錄偷當(dāng)前房屋的最大金額即dfs(i + 2) + nums[i]
- 返回ans1與ans2的較大值
- 邊界情況：當(dāng)i>=len時(shí)表示無(wú)房屋可偷返回0
- 所求值： dfs(0)表示從第0個(gè)房屋開始偷竊能夠獲得的最大金額
class Solution:
def rob(self, nums: List[int]) -> int:
def dfs(i)-> int:
if i >= len(nums):
return 0
# 不偷當(dāng)前房屋
ans1 = dfs(i + 1)
# 偷當(dāng)前房屋
ans2 = dfs(i + 2) + nums[i]
return max(ans1, ans2)
return dfs(0)
按照上述的遞歸方式可以得到最大金額，但我們?cè)贚eetCode上會(huì)發(fā)現(xiàn)該方法超出時(shí)間限制。
如上圖所示，我們對(duì)于選2這個(gè)分支計(jì)算了兩次，那么如果房屋個(gè)數(shù)n更多，我們就會(huì)重復(fù)計(jì)算多次，這樣會(huì)浪費(fèi)大量的時(shí)間，故超出時(shí)間限制。
如果我們?cè)诘谝淮斡?jì)算時(shí)，使用數(shù)組記錄選擇2的最大金額來(lái)保存計(jì)算結(jié)果，這樣就可以避免重復(fù)計(jì)算，而這就是動(dòng)態(tài)規(guī)劃的精髓：遞歸搜索+保存計(jì)算結(jié)果=記憶化搜索。
遞歸+記憶化搜索
- 遞歸函數(shù)定義：dfs(i)函數(shù)表示
從第i個(gè)房屋開始偷竊能夠獲得的最大金額 - 狀態(tài)轉(zhuǎn)移方程：ans1記錄不偷當(dāng)前房屋的最大金額即dfs(i + 1)，ans2記錄不偷當(dāng)前房屋的最大金額即dfs(i + 2) + nums[i]，dfs(i)為ans1與ans2的較大值即狀態(tài)轉(zhuǎn)移方程：dfs(i) =max (dfs(i - 1), dfs(i-2)+ nums[i])
- 邊界條件：當(dāng)i>=len時(shí)表示無(wú)房屋可偷返回0
- 所求值： dfs(0)表示從第0個(gè)房屋開始偷竊能夠獲得的最大金額。
class Solution:
def rob(self, nums: List[int]) -> int:
# python的@cache裝飾器可以用來(lái)寄存函數(shù)對(duì)已處理參數(shù)的結(jié)果，以便遇到相同參數(shù)可以直接給出答案。
@cache
def dfs(i: int) -> int:
if i >len(nums)-1: return 0
return max(dfs(i + 1), dfs(i + 2) + nums[i])
return dfs(0)
遞歸dfs()1:1 轉(zhuǎn)換成迭代dp[]數(shù)組
如果一個(gè)動(dòng)態(tài)規(guī)劃問題可以用自底向上的方法求解，那么它通常可以從遞歸轉(zhuǎn)換為迭代。
遞歸到迭代的轉(zhuǎn)換是通過以下步驟實(shí)現(xiàn)的：
- 分析遞歸解法中的狀態(tài)轉(zhuǎn)移方程。在上述動(dòng)態(tài)規(guī)劃代碼片段中，狀態(tài)轉(zhuǎn)移方程為：
dfs(i) = max(dfs(i - 1), dfs(i - 2) + nums[i])。 - 使用一個(gè)數(shù)組 dp[] 來(lái)存儲(chǔ)子問題的解。數(shù)組的長(zhǎng)度為len(nums) + 2，這是為了處理邊界情況。
- 使用迭代的方式，自底向上計(jì)算子問題的解，如從前往后遍歷數(shù)組，根據(jù)狀態(tài)轉(zhuǎn)移方程計(jì)算每個(gè)子問題的解，并將結(jié)果存儲(chǔ)在數(shù)組中如本題我們可以通過
for i, x in enumerate(nums): dp[i + 2] = max(dp[i + 1],dp[i] + x)來(lái)迭代記錄，與狀態(tài)轉(zhuǎn)移方程對(duì)比，我們可以發(fā)現(xiàn)改變的只將dfs全部換為了f[]數(shù)組記錄，其次就是i的起始值會(huì)變化。
class Solution:
def rob(self, nums: List[int]) -> int:
dp = [0] * (len(nums) + 2)
for i, x in enumerate(nums):
dp[i + 2] = max(dp[i + 1], dp[i] + x)
return dp[-1]
空間優(yōu)化——滾動(dòng)數(shù)組dp[i]轉(zhuǎn)換為有限變量f0與f1
因?yàn)檫f推函數(shù)dp[i + 2] = max(dp[i + 1], dp[i] + x) 只依賴于前兩個(gè)值dp[i + 1]和dp[i] + x)，因此我們可以用f0與f1來(lái)循環(huán)記錄中間結(jié)果。
當(dāng)動(dòng)態(tài)規(guī)劃問題具有這種“滾動(dòng)數(shù)組”特性時(shí)，通?？梢酝ㄟ^使用有限數(shù)量的變量來(lái)減少空間復(fù)雜度。
class Solution:
def rob(self, nums: List[int]) -> int:
f0 = f1 = 0
for i, x in enumerate(nums):
f0, f1 = f1, max(f1, f0 + x)
return f1
總結(jié)
如果不是很熟悉動(dòng)態(tài)規(guī)劃，在進(jìn)行做題時(shí)可以采用示例的思路，首先思考只考慮遞歸該如何解決該題，之后1:1轉(zhuǎn)換為迭代dp[]數(shù)組做動(dòng)態(tài)規(guī)劃，最后考慮是否可以進(jìn)行空間優(yōu)化。
算法練習(xí)一：LeetCode70. 爬樓梯
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
遞歸+記憶化搜索
要求當(dāng)前n層有多少種方法，每次可以走1或2臺(tái)階，即我們可以得出遞推函數(shù)為dfs(i) =dfs(i - 1)+dfs(i-2)，dfs(i)代表的是從第i個(gè)階梯開始爬樓梯能夠到達(dá)頂部的不同方法數(shù)。當(dāng) n 等于 1 或 2 時(shí)，直接返回 1 或 2。否則，遞歸調(diào)用 climbStairs(n-1) 和 climbStairs(n-2)，并將它們的結(jié)果相加。
class Solution:
@cache
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
elif n == 2:
return 2
else:
return self.climbStairs(n-1) + self.climbStairs(n-2)
遞歸dfs()1:1 轉(zhuǎn)換成迭代dp[]數(shù)組
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0] * (n + 2)
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
空間優(yōu)化——滾動(dòng)數(shù)組dp[i]轉(zhuǎn)換為有限變量f0與f1
由示例可知本題可以直接進(jìn)行空間優(yōu)化
func climbStairs(n int) int {
if n==1{
return 1
}
f0,f1:=1,2
for i:=2;i<n;i++{
f0,f1=f1,f0+f1
}
return f1
}
算法練習(xí)二：LeetCode213. 打家劫舍 II
你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋，每間房?jī)?nèi)都藏有一定的現(xiàn)金。這個(gè)地方所有的房屋都 圍成一圈 ，這意味著第一個(gè)房屋和最后一個(gè)房屋是緊挨著的。同時(shí)，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警 。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你 在不觸動(dòng)警報(bào)裝置的情況下 ，今晚能夠偷竊到的最高金額。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-608307.html
按照選或不選的思路分類討論:文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-608307.html
- 如果選即偷nums[0]，那么nums[1]和nums(n 一1]不能偷，問題變成從nums[2]到nums[n -2]的非環(huán)形版本，調(diào)用示例即198題的代碼解決;
- 如果不選即不偷nums(0]，那么問題變成從naums[1]到numsn -1]的非環(huán)形版本，同樣調(diào)用示例即198題的代碼解決。
func rob1(nums []int, start, end int) int {
f0, f1 := 0, 0
for i := start; i < end; i++ {
f0, f1 = f1, max(f1, f0+nums[i])
}
return f1
}
func rob(nums []int) int {
n := len(nums)
return max(nums[0]+rob1(nums, 2, n-1), rob1(nums, 1, n))
}
func max(a, b int) int { if b > a { return b }; return a }
到了這里，關(guān)于算法套路十三——?jiǎng)討B(tài)規(guī)劃DP入門的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
