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

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

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

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

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

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

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

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

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

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

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

示例：

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

來看看具體的動圖演示：

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

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

4. 推導動態(tài)規(guī)劃狀態(tài)轉移方程

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

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

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

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

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

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

此時對應的狀態(tài)轉移方程如下：$A_i>F_{i-1,k-1}$，則 $F_{i,k}=min(A_i,F_{i-1,k})$，否則$F_{i,k}=F_{i-1,k}$。大家可以自行思考下這個狀態(tài)轉移方程，動筆畫一畫。

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

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

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

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

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

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

注意：每次只能向下或者向右移動一步。

示例：

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

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

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

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

$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)$

于是得到最后的動態(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] 
        
        # 動態(tài)轉移方程
        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]

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

6. 小結

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

Tips：文中動圖制作參考：https://visualgo.net/zh/sorting。