動(dòng)態(tài)規(guī)劃算法介紹

今天我們來介紹基礎(chǔ)算法中非常重要而且又略微燒腦的算法：動(dòng)態(tài)規(guī)劃 (Dynamic Programming, 簡(jiǎn)稱DP) 算法。

1. 動(dòng)態(tài)規(guī)劃算法介紹

動(dòng)態(tài)規(guī)劃算法的基本思想與分治法類似，也是將待求解的問題分解為若干個(gè)子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。

在求解任一子問題時(shí)，列出各種可能的局部解，通過決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個(gè)子問題就是初始問題的解。

2. 動(dòng)態(tài)規(guī)劃算法過程

動(dòng)態(tài)規(guī)劃過程是：每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，因此，這種多階段最優(yōu)化決策解決問題的過程就稱為動(dòng)態(tài)規(guī)劃。

動(dòng)態(tài)規(guī)劃的本質(zhì)，是對(duì)問題狀態(tài)的定義和狀態(tài)轉(zhuǎn)移方程的定義。動(dòng)態(tài)規(guī)劃是通過拆分問題，定義問題狀態(tài)和狀態(tài)之間的關(guān)系，使得問題能夠以遞推（或者說分治）的方式去解決。因此在一個(gè)典型的動(dòng)態(tài)規(guī)劃問題上，我們需要能定義問題狀態(tài)以及寫出狀態(tài)轉(zhuǎn)移方程，這樣對(duì)于該問題的解答就會(huì)一目了然。我們用一個(gè)經(jīng)典的最長(zhǎng)上升子序列問題對(duì)此進(jìn)行說明。

3. 舉例說明動(dòng)態(tài)規(guī)劃算法

最長(zhǎng)上升子序列 (LIS) 問題如下：

給定一個(gè)無序的整數(shù)數(shù)組，找到其中最長(zhǎng)上升子序列的長(zhǎng)度。

示例：

輸入：[10, 9, 2, 5, 3, 7, 101, 18]
輸出：4 
解釋：最長(zhǎng)的上升子序列是 [2,3,7,101]，它的長(zhǎng)度是 4。

來看看具體的動(dòng)圖演示：

對(duì)于這個(gè)非常典型的動(dòng)態(tài)規(guī)劃問題，我們首先考慮如何定義問題的狀態(tài)。一種簡(jiǎn)單的狀態(tài)定義如下：

$f(x)$ 為以 $a_x$ 結(jié)尾的 LIS 長(zhǎng)度,那么 LIS 的答案就是$max\{f(x)\}$

4. 推導(dǎo)動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程

有了這樣一個(gè)狀態(tài)定義，我們來推導(dǎo)狀態(tài)轉(zhuǎn)移方程。來看如下示意圖：

從上面的圖中，我們可以很明顯得到該問題的狀態(tài)轉(zhuǎn)義方程，如下：
$F(x) = max_{p<x,a_p<a_x}\{F(p) + 1\}$
于是有了這個(gè)狀態(tài)方程我們就能很快寫出相關(guān)的代碼：

def lengthOfLIS(self, nums):
    if not nums:
        return 0

    n = 1
    F = [1]
    for i in range(1, len(nums)):
        max_num = 1
        for j in range(i - 1, -1, -1):
            if nums[i] > nums[j] and max_num < (F[j] + 1):
                max_num = F[j] + 1
                F.append(max_num)
        if F[-1] > n:
            n = F[-1]
    return n

這里的平均時(shí)間復(fù)雜度很明顯為 $O(n^2)$。此外，對(duì)于該問題，我們還可以以另外一種角度考慮該問題，并定義一種二維狀態(tài)：

給定一個(gè)數(shù)列，長(zhǎng)度為 N，設(shè) $F_{i,k}$ 為：在前i項(xiàng)中的，長(zhǎng)度為k的最長(zhǎng)遞增子序列中，最后一位的最小值為：$1 \leq{k}\leq{N}$

注意：若在前 i 項(xiàng)中，不存在長(zhǎng)度為 k 的最長(zhǎng)遞增子序列，則 $F_{i,k}$ 為正無窮.求最大的 x，使得 $F_{N,x}$ 不為正無窮。

此時(shí)對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移方程如下：$A_i>F_{i-1,k-1}$，則 $F_{i,k}=min(A_i,F_{i-1,k})$，否則$F_{i,k}=F_{i-1,k}$。大家可以自行思考下這個(gè)狀態(tài)轉(zhuǎn)移方程，動(dòng)筆畫一畫。

5. 動(dòng)態(tài)規(guī)劃的深入理解

文獻(xiàn)1中的第一個(gè)回答給出了動(dòng)態(tài)規(guī)劃的一些基本性質(zhì)以及如何判斷一個(gè)問題是否能使用 DP 解決。首先是基礎(chǔ)概念：

• 無后效性：嚴(yán)格定義就是如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響。也就是說未來與過去無關(guān)，這就是無后效性。
• 最優(yōu)子結(jié)構(gòu)：大問題的最優(yōu)解可以由小問題的最優(yōu)解推出，這個(gè)性質(zhì)叫做最優(yōu)子結(jié)構(gòu)性質(zhì)。

有了這兩個(gè)概念之后，判斷一個(gè)問題能否使用 DP 解決，就看該問題能否滿足如下條件：大問題能拆成幾個(gè)小問題，且滿足無后效性、最優(yōu)子結(jié)構(gòu)性質(zhì)。

我們以 leetcode 上的第 64 題最小路徑和為例進(jìn)行說明：

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

注意：每次只能向下或者向右移動(dòng)一步。

示例：

輸入:
[
    [1,3,1],
    [1,5,1],
    [4,2,1]
]
輸出: 7
解釋: 因?yàn)槁窂?1→3→1→1→1 的總和最小。

以上面的示例為例，我們首先看這個(gè)最小路徑問題：

能理解該問題滿足 DP 的兩個(gè)特性，所以能用動(dòng)態(tài)規(guī)劃方法解決。我們定義狀態(tài)：$F[i][j]$表示到$(i,j)$位置的最小路徑和。

那么狀態(tài)方轉(zhuǎn)移方程也非常清楚，正如圖中所示：
$F[i][j]=min(F[i-1][j], F[i][j-1]) + 1$
確定了核心步驟后，我們來看看問題的初始條件，類似于遞歸方法的終止條件。注意到每次只能向下或者向右移動(dòng)一次，因此：

$F[i][0] = F[i-1][0] + grid[i][0] (i > 0) \;|\; grid[0][0](i=0) F[0][j] = F[0][j-1] + grid[0][j] (j > 0) \;|\; grid[0][0](j=0)$

于是得到最后的動(dòng)態(tài)規(guī)劃代碼如下：

class Solution:
    def minPathSum(self, grid):
        if not grid:
            return 0

        F = []
        for i in range(len(grid)):
            F.append([0] * len(grid[0]))

        # 邊界條件，向下
        for i in range(len(grid)):
            if i == 0:
                F[i][0] = grid[i][0]
            else:
                F[i][0] = F[i - 1][0] + grid[i][0]
        # 邊界條件，向右
        for j in range(len(grid[0])):
            if  j == 0:
                F[0][j] = grid[0][j]
            else:
                F[0][j] = F[0][j - 1] + grid[0][j] 
        
        # 動(dòng)態(tài)轉(zhuǎn)移方程
        for i in range(1, len(grid)):
            for j in range(1, len(grid[0])):
                F[i][j] = min(F[i - 1][j], F[i][j-1]) + grid[i][j]
        
        return F[-1][-1]

這題是一個(gè)二維 DP 的典型例題，非常有代表性?？偨Y(jié)而言，對(duì)于 DP 問題，我們首先是分析該問題能否使用 DP 方法去解答。如果可以，就需要思考和定義問題的狀態(tài)定義并找出狀態(tài)轉(zhuǎn)移方程。有了這些核心的步驟后，我們只需要再分析以下初始的邊界條件，然后就可以動(dòng)手開始實(shí)現(xiàn)該問題的 DP 代碼了。

6. 小結(jié)

本節(jié)我們介紹了動(dòng)態(tài)規(guī)劃算法的相關(guān)概念以及涉及到的解題步驟，然后用兩個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃例子展示了一般動(dòng)態(tài)規(guī)劃問題的求解步驟。接下來我們會(huì)用 leetcode 上的習(xí)題進(jìn)行動(dòng)態(tài)規(guī)劃實(shí)戰(zhàn)，加深對(duì)其理解并熟練使用。

Tips：文中動(dòng)圖制作參考：https://visualgo.net/zh/sorting。