動(dòng)態(tài)規(guī)劃算法實(shí)戰(zhàn)

本小節(jié)會(huì)以 leetcode 上的 4 道編程題來進(jìn)行動(dòng)態(tài)規(guī)劃算法的實(shí)戰(zhàn)，以幫助大家更好的理解和掌握動(dòng)態(tài)規(guī)劃算法。

1. 一維DP

1.1 題目1：買賣股票的最佳時(shí)機(jī)

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

如果你最多只允許完成一筆交易（即買入和賣出一支股票一次），設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)。

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

示例 1：

輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第2天（股票價(jià)格=1）的時(shí)候買入，在第5天（股票價(jià)格=6）的時(shí)候賣出，最大利潤(rùn)=6-1=5 。注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格；同時(shí)，你不能在買入前賣出股票。

示例 2：

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

這樣的典型一維 DP 問題，我們會(huì)先思考下如何定義問題的狀態(tài)，如何能得到遞推關(guān)系？假設(shè)我定義這樣一個(gè)和股票數(shù)據(jù)相同大小的列表 F[x]，表示以位置 x 結(jié)尾時(shí)能獲得的最大利潤(rùn)，將這個(gè)作為問題的狀態(tài)。容易分析其狀態(tài)轉(zhuǎn)移方程如下，其中 minVal 等于 nums[0:x-1] 中的最小值：
$F[x]=max(F[x-1],nums[x]-minVal)$
示意圖如下：

初始的狀態(tài)條件自然是 F[0] = 0，接下來我們根據(jù)上面的 DP 過程完成相應(yīng)的代碼，如下：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0: return 0 
        dp = [0] * n
        minVal = prices[0] 

        for i in range(1, n):
            minVal = min(minVal, prices[i])
            dp[i] = max(dp[i - 1], prices[i] - minVal)

        return dp[-1]

1.2 題目2：打家劫舍

你是一個(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)能夠偷竊到的最高金額。

示例 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 。

這個(gè)同樣也是一維 DP 問題，我們這樣思考下，定義兩個(gè)狀態(tài)數(shù)組 F 和 M，其含義分別如下：

• $F[x]$：小偷偷竊到 x 位置的房屋為止，且最后偷竊 x 位置的房屋，此時(shí)偷竊的最大金額值
• $M[x]$：小偷偷竊到 x 位置的房屋為止，且最后沒有偷竊 x 位置的房屋，此時(shí)偷竊的最大金額值

那這樣可以得到這樣的遞推方程：
$\begin{aligned} &F[x] = M[x-1] + nums[x]\\ &M[x] = max(F[x-1], M[x-1]) \end{aligned}$
最后我們的結(jié)果為：
$result = max(F[-1], M[-1])$
這樣可以得到如下的 DP 代碼：

class Solution:
    def rob(self, nums):
        if not nums:
            return 0
		# 初始條件
        F = [0] * len(nums)
        M = [0] * len(nums)
        
        # 初始條件
        F[0] = nums[0]
        M[0] = 0
        for i in range(1, len(nums)):
            # 得到狀態(tài)轉(zhuǎn)移方程
            F[i] = M[i - 1] + nums[i]
            M[i] = max(F[i - 1], M[i - 1])
        # 返回最后結(jié)果    
        return max(F[-1], M[-1])

2. 二維 DP

2.1 題目1：不同路徑

一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。問總共有多少條不同的路徑？

這題和前面遞歸中講解的爬樓梯問題非常相似，我們也可以和之前一樣使用遞歸算法完成解答。但是爬樓梯以及該問題中使用遞歸存在大量的重復(fù)計(jì)算，我們要考慮是用 DP 方法來解決該問題。這是一個(gè)二維的網(wǎng)格，因此對(duì)于 DP 問題而言，我們要考慮二維 DP。定義如下二維 DP 數(shù)組 $P[i][j]$ ，表示到$(i,j)$位置的不同路徑數(shù)。

有了這樣一個(gè)狀態(tài)的定義，來看相應(yīng)的遞歸方程。注意到機(jī)器人只能向下或者向右移動(dòng)一步，因此有：

$P[i][j]=P[i-1][j] + P[i][j-1]$

初始狀態(tài)也非常容易，有：

$\begin{aligned} &P[i][0]=1(i=0,\cdots,m)\\ &P[0][j]=1(j=0,\cdots,n) \end{aligned}$
于是可以立馬寫出相應(yīng)的 DP 答案：

class Solution:
    def uniquePaths(self, m, n):
        if not m or not n:
            return 0

        P = []
        # 保證 P[i][0]=1,P[0][j]=1，即可。其余位置將會(huì)遞推得到
        for i in range(m):
            P.append([1] * n)

        # 動(dòng)態(tài)轉(zhuǎn)移方程
        for i in range(1, m):
            for j in range(1, n):
                P[i][j] = P[i-1][j] + P[i][j-1]
        
        return P[-1][-1]
        

2.2 題目2：最長(zhǎng)公共子序列(LCS)

給定兩個(gè)字符串 text1 和 text2，返回這兩個(gè)字符串的最長(zhǎng)公共子序列的長(zhǎng)度。

一個(gè)字符串的子序列是指這樣一個(gè)新的字符串：它是由原字符串在不改變字符的相對(duì)順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。兩個(gè)字符串的「公共子序列」是這兩個(gè)字符串所共同擁有的子序列。

若這兩個(gè)字符串沒有公共子序列，則返回 0。

示例1：

輸入：text1 = "abcde", text2 = "ace" 
輸出：3  
解釋：最長(zhǎng)公共子序列是 "ace"，它的長(zhǎng)度為 3。

示例2：

輸入：text1 = "abc", text2 = "abc"
輸出：3
解釋：最長(zhǎng)公共子序列是 "abc"，它的長(zhǎng)度為 3。

示例3：

輸入：text1 = "abc", text2 = "def"
輸出：0
解釋：兩個(gè)字符串沒有公共子序列，返回 0。

這個(gè)也是非常經(jīng)典的一道面試題，它的解法也是典型的二維動(dòng)態(tài)規(guī)劃。我們繼續(xù)按照上面的步驟來定義問題的狀態(tài)數(shù)組以及推導(dǎo)相應(yīng)的狀態(tài)轉(zhuǎn)移方程。

我們和前面一樣用一個(gè)二維的狀態(tài)矩陣來遞推該問題，假設(shè)二維狀態(tài)矩陣如下：

• $P[i][j]$：表示 text1[0:i] 和 text2[0:j] 的最長(zhǎng)公共子序列的長(zhǎng)度。

現(xiàn)在來看圖說明該二維狀態(tài)矩陣以及從中推導(dǎo)出狀態(tài)轉(zhuǎn)移方程：

容易遞推出狀態(tài)轉(zhuǎn)移方程：
$\begin{aligned} &P[i][j]=P[i-1][j-1]+1(text1[i]==text2[j]) \\ &or \; max(P[i-1][j], P[i][j-1])(text1[i]!=text2[j]) \end{aligned}$
這樣我們很容易就能寫出相應(yīng)的 DP 代碼，如下：

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2:
            return 0

        # 初始狀態(tài)矩陣
        P = []
        for _ in range(len(text1)):
            P.append([0] * len(text2))
        
        # 編寫初始狀態(tài)，以下兩個(gè)for循環(huán)主要是處理一些邊界問題
        for j in range(len(text2)):
            if j == 0:
                P[0][j] = 1 if text2[j] == text1[0] else 0
            else:
                P[0][j] = max(P[0][j-1], 1 if text2[j] == text1[0] else 0) 
        
        for i in range(len(text1)):
            if i == 0:
                P[i][0] = 1 if text1[i] == text2[0] else 0
            else:
                P[i][0] = max(P[i-1][0], 1 if text1[i] == text2[0] else 0) 

        # 核心部分，狀態(tài)轉(zhuǎn)移方程
        for i in range(1, len(text1)):
            for j in range(1, len(text2)):
                # 上面圖片中推到的狀態(tài)轉(zhuǎn)移方程
                if text1[i] == text2[j]:
                    P[i][j] = P[i-1][j-1] + 1
                else:
                    P[i][j] = max(P[i-1][j], P[i][j-1])

        return P[-1][-1]

3. 小結(jié)

本小節(jié)中我們以 4 道代表性題目給大家展示了如何求解動(dòng)態(tài)規(guī)劃問題，在 leetcode 上還有許許多多更為復(fù)雜和為燒腦的動(dòng)態(tài)規(guī)劃題目，大家要多多練習(xí)，達(dá)到熟能生巧的地步。