動態(tài)規(guī)劃（Dynamic Programming）題目特點

1. 計數

• 有多少種方式走到右下角
• 有多少種方法選出k個數使得和是Sum

2. 求最大最小值

• 從左上角走到右下角路徑的最大數字和
• 最長上升子序列長度

3. 求存在性

• 取石子游戲，先手是否必勝
• 能不能選出k個數使得和是Sum

例1：硬幣組合——最大最小值動態(tài)規(guī)劃

題目描述：
你有三種硬幣，分別面值2元，5元和7元，每種硬幣都有足夠多
? 買一本書需要27元
? 如何用最少的硬幣組合正好付清，不需要對方找錢。

直覺：
最少硬幣組合 → 盡量用面值大的硬幣
? 7+7+7 = 21
? 21 + 5 = 26
? 呃。。。

改進：
盡量用大的硬幣，最后如果可以用一種硬幣付清就行
? 7+7+7 = 21
? 21 + 2 + 2 + 2 = 27
? 6枚硬幣，應該對了吧。。。

然而，正確答案：7 + 5 + 5 + 5 + 5 = 27，5枚硬幣。

動態(tài)規(guī)劃組成部分一：確定狀態(tài)

狀態(tài)在動態(tài)規(guī)劃中的作用屬于定海神針。簡單的說，解動態(tài)規(guī)劃的時候需要開一個數組，數組的每個元素 f[i] 或者 f[i][j] 代表什么，類似于解數學題中，X，Y，Z代表什么。確定狀態(tài)需要兩個意識：最后一步和子問題。

• 最后一步

雖然我們不知道最優(yōu)策略是什么，但是最優(yōu)策略肯定是 K 枚硬幣 a1, a2,…, aK 面值加起來是27，所以一定有一枚最后的硬幣 aK。除掉這枚硬幣，前面硬幣的面值加起來是27- aK。

我們不關心前面的K-1枚硬幣是怎么拼出27- aK 的（可能有1種拼法，可能有 100種拼法），而且我們現在甚至還不知道 aK 和 K，但是我們確定前面的硬幣拼出了 27- aK 。因為是最優(yōu)策略，所以拼出27- aK 的硬幣數一定要最少，否則這就不是最優(yōu)策略了。

• 子問題

所以我們就要求：最少用多少枚硬幣可以拼出27- aK。原問題是最少用多少枚硬幣拼出27，我們將原問題轉化成了一個子問題，而且規(guī)模更小：27- aK。為了簡化定義，我們設狀態(tài) f(X) 等于最少用多少枚硬幣拼出X。

等等，我們還不知道最后那枚硬幣aK是多少。最后那枚硬幣 aK 只可能是2，5或者7。如果 aK 是2，f(27)應該是f(27-2) + 1 (加上最后這一枚硬幣2）；如果 aK 是5，f(27)應該是f(27-5) + 1 (加上最后這一枚硬幣5）；如果 aK 是7，f(27)應該是f(27-7) + 1 (加上最后這一枚硬幣7）。除此以外，沒有其他的可能了 。

需要求最少的硬幣數，所以： f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}

基于上述分析，可以使用遞歸的方式來解決：

def coin_change_re(x):
    if x == 0:
        return 0
    res = 1e15
    if x >= 2:
        res = min(ch_coin_re(x-2)+1, res)
    if x >= 5:
        res = min(ch_coin_re(x-5)+1, res)
    if x >= 7:
        res = min(ch_coin_re(x-7)+1, res)
    return res

但是有很多重復計算，效率低下。下圖計算了三次f(20)：

解決方式：將計算結果保存下來，并改變計算順序。

動態(tài)規(guī)劃組成部分二：轉移方程

設狀態(tài)f[X]=最少用多少枚硬幣拼出X 。

動態(tài)規(guī)劃組成部分三：初始條件和邊界情況

f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}

兩個問題：
X-2, X-5 或者X-7小于0怎么辦？什么時候停下來？
如果不能拼出Y，就定義f[Y]=正無窮。例如f[-1]=f[-2]=…=正無窮

所以：
初始條件：f[0] = 0
f[1] =min{f[-1]+1, f[-4]+1,f[-6]+1}=正無窮, 表示拼不出來1

動態(tài)規(guī)劃組成部分四：計算順序

? 拼出X所需要的最少硬幣數：f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}
? 初始條件：f[0] = 0
? 然后計算f[1], f[2], …, f[27]
? 當我們計算到f[X]時，f[X-2], f[X-5], f[X-7]都已經得到結果了。

f[0] = 0
f[1] = min{f[-1]+1, f[-4]+1,f[-6]+1} = ∞
f[2] = min{f[0]+1, f[-3]+1,f[-5]+1} = 1
f[3] = min{f[1]+1, f[-2]+1,f[-4]+1} = ∞
f[4] = min{f[2]+1, f[-1]+1,f[-3]+1} = 2
f[5] = min{f[3]+1, f[0]+1,f[-2]+1} = 1
f[6] = min{f[4]+1, f[1]+1,f[-1]+1} = 3
……
f[27] = 5

每一步嘗試三種硬幣，一共27步。與遞歸算法相比，沒有任何重復計算。算法時間復雜度（即需要進行的步數）： 面額數x硬幣種類。這里是27x3。

代碼如下：

def coin_change(coins, amount):
    """
    換零錢動態(tài)規(guī)劃算法
    :param coins: 零錢種類整數列表
    :param amount: 需要換的面值
    :return: 最少換取的硬幣數
    """
    MAX_VALUE = 1e15
    states = [MAX_VALUE] * (amount+1)  # 狀態(tài)數組初始化，包含狀態(tài)0
    states[0] = 0  # 初始值為0
    for i in range(1, amount+1):  # 依次求每個狀態(tài)
        for coin in coins:  # 遍歷所有硬幣種類，求最小值
            if i - coin < 0:
                continue
            states[i] = min(states[i], states[i-coin]+1)
    if states[amount] == MAX_VALUE:
        return -1
    return states[amount]

小結

求最值型動態(tài)規(guī)劃，動態(tài)規(guī)劃組成部分：

1. 確定狀態(tài)
   ? 最后一步（最優(yōu)策略中使用的最后一枚硬幣aK）
   ? 化成子問題（最少的硬幣拼出更小的面值27-aK）
2. 轉移方程
   ? f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}
3. 初始條件和邊界情況
   ? f[0] = 0
   ? 如果不能拼出Y，f[Y]=正無窮
4. 計算順序
   ? f[0], f[1], f[2], …

例2：不同的路徑數——計數型動態(tài)規(guī)劃

題目描述：
給定m行n列的網格，有一個機器人從左上角(0,0)出發(fā)，每一步可以向下 或者向右走一步，問有多少種不同的方式走到右下角。

組成部分一：確定狀態(tài)

• 最后一步：無論機器人用何種方式到達右下角，總有最后挪動的一步：向右或者向下。右下角坐標設為(m-1, n-1) ，那么前一步機器人一定是在(m-2, n-1)或者(m-1, n-2) 。

• 子問題：如果機器人有X種方式從左上角走到(m-2,n-1)，有Y種方式從左上 角走到(m-1,n-2)，則機器人有X+Y種方式走到(m-1, n-1)。問題轉化為，機器人有多少種方式從左上角走到(m-2, n-1)和(m-1, n-2)。原題要求有多少種方式從左上角走到(m-1, n-1)。

• 狀態(tài)：設 f[i][j] 為機器人有多少種方式從左上角走到(i, j)。

組成部分二：轉移方程

組成部分三：初始條件和邊界情況

• 初始條件：f[0][0] = 1，因為機器人只有一種方式到左上角（什么都不做）
• 邊界情況：i = 0 或 j = 0，則前一步只能有一個方向過來。

組成部分四：計算順序

• f[0][0] = 1
• 計算第0行：f[0][0], f[0][1], …, f[0][n-1]
• 計算第1行：f[1][0], f[1][1], …, f[1][n-1]
  …
• 計算第m-1行：f[m-1][0], f[m-1][1], …, f[m-1][n-1]
• 答案是f[m-1][n-1]
• 時間復雜度（計算步數）：O(MN)，空間復雜度（數組大?。篛(MN)

代碼如下：

def unique_paths(m, n):
    """
    :param m: 網格行數
    :param n: 網格列數
    :return: 從左上角到右下角所有的路徑數
    """
    states = [[0] * n] * m  # 狀態(tài)數組
    states[0][0] = 1
    for i in range(m):
        for j in range(n):
            if i == 0 or j == 0:  # 邊界處都只有一條路可走
                states[i][j] = 1
            else:
                states[i][j] = states[i - 1][j] + states[i][j-1]
    return states[m-1][n-1]

例3：跳躍游戲——存在型動態(tài)規(guī)劃

題目描述：
有n塊石頭分別在x軸的0, 1, …, n-1位置，一只青蛙在石頭0，想跳到石頭n-1。如果青蛙在第 i 塊石頭上，它最多可以向右跳距離ai 。問青蛙能否跳到石頭n-1？
例子：
輸入：a=[2, 3, 1, 1, 4] 輸出：True
輸入：a=[3, 2, 1, 0, 4] 輸出：False

組成部分一：確定狀態(tài)

• 最后一步：如果青蛙能跳到最后一塊石頭n-1，我們考慮它跳的最后一步，這一步是從石頭i跳過來，i<n-1。這需要兩個條件同時滿足：青蛙可以跳到石頭i；最后一步不超過跳躍的最大距離：n-1-i<=ai 。

• 子問題：那么，我們需要知道青蛙能不能跳到石頭i (i<n-1)，而我們原來要求青蛙能不能跳到石頭n-1。

• 狀態(tài)：設 f[j] 表示青蛙能不能跳到石頭 j 。

組成部分二：轉移方程

組成部分三：初始條件和邊界情況

初始條件：f[0] = True，因為青蛙一開始就在石頭0。

組成部分四：計算順序

? 設f[j]表示青蛙能不能跳到石頭j
?
? 初始化 f[0]=True
? 計算 f[1], f[2], …, f[n-1]
? 答案是 f[n-1]
? 時間復雜度：O(N²)，空間復雜度（數組大?。篛(N)

代碼如下：

def jump_game(n, lst):
    states = [False] * n
    states[0] = True
    for i in range(1, n):
        for j in range(i):
            if states[j] and lst[j] + j >= i:
                states[i] = True
                break
    return states[n-1]

以上代碼時間復雜度為 O(N²)，一般會運行超時，但是也是需要掌握的。優(yōu)化后的代碼（時間復雜度O(N)）：

 def jump_game(n, lst):
        max_reach = 0
        for i, x in enumerate(lst): 
            if max_reach < i: return False # 如果之前的最遠距離下標，小于當前的下標，就gg
            if max_reach >= n - 1: return True # 或者大于最遠直接返回True
            max_reach = max(max_reach, i + x)  # 每一步更新可以跳到的最遠距離下標

總結

四個組成部分：

• 確定狀態(tài)
  ? 研究最優(yōu)策略的最后一步
  ? 化為子問題
• 轉移方程
  ? 根據子問題定義直接得到
• 初始條件和邊界情況
  ? 細心，考慮周全
• 計算順序
  ? 利用之前的計算結果

常見動態(tài)規(guī)劃類型：

• 坐標型動態(tài)規(guī)劃 (20%)
• 序列型動態(tài)規(guī)劃 (20%)
• 劃分型動態(tài)規(guī)劃 (20%)
• 區(qū)間型動態(tài)規(guī)劃 (15%)
• 背包型動態(tài)規(guī)劃 (10%)
• 拓撲型動態(tài)規(guī)劃 (5%)
• 博弈型動態(tài)規(guī)劃 (5%)
• 綜合性動態(tài)規(guī)劃 (5%)