動態(tài)規(guī)劃（Dynamic Programming）題目特點
1. 計數(shù)
- 有多少種方式走到右下角
- 有多少種方法選出k個數(shù)使得和是Sum
2. 求最大最小值
- 從左上角走到右下角路徑的最大數(shù)字和
- 最長上升子序列長度
3. 求存在性
- 取石子游戲乒裆，先手是否必勝
- 能不能選出k個數(shù)使得和是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枚硬幣，應(yīng)該對了吧丐黄。斋配。。
然而灌闺，正確答案：7 + 5 + 5 + 5 + 5 = 27艰争，5枚硬幣。
動態(tài)規(guī)劃組成部分一：確定狀態(tài)
狀態(tài)在動態(tài)規(guī)劃中的作用屬于定海神針桂对。簡單的說甩卓，解動態(tài)規(guī)劃的時候需要開一個數(shù)組，數(shù)組的每個元素 f[i] 或者 f[i][j] 代表什么接校，類似于解數(shù)學題中猛频，X，Y蛛勉，Z代表什么鹿寻。確定狀態(tài)需要兩個意識：最后一步和子問題。
- 最后一步
雖然我們不知道最優(yōu)策略是什么诽凌，但是最優(yōu)策略肯定是 K 枚硬幣 a1, a2,…, aK 面值加起來是27毡熏，所以一定有一枚最后的硬幣 aK。除掉這枚硬幣侣诵，前面硬幣的面值加起來是27- aK痢法。
我們不關(guān)心前面的K-1枚硬幣是怎么拼出27- aK 的（可能有1種拼法，可能有 100種拼法）杜顺，而且我們現(xiàn)在甚至還不知道 aK 和 K财搁，但是我們確定前面的硬幣拼出了 27- aK 。因為是最優(yōu)策略躬络，所以拼出27- aK 的硬幣數(shù)一定要最少尖奔，否則這就不是最優(yōu)策略了。
- 子問題
所以我們就要求：最少用多少枚硬幣可以拼出27- aK穷当。原問題是最少用多少枚硬幣拼出27提茁，我們將原問題轉(zhuǎn)化成了一個子問題，而且規(guī)模更心俨恕：27- aK茴扁。為了簡化定義，我們設(shè)狀態(tài) f(X) 等于最少用多少枚硬幣拼出X汪疮。
等等峭火，我們還不知道最后那枚硬幣aK是多少毁习。最后那枚硬幣 aK 只可能是2，5或者7卖丸。如果 aK 是2蜓洪，f(27)應(yīng)該是f(27-2) + 1 (加上最后這一枚硬幣2）；如果 aK 是5坯苹，f(27)應(yīng)該是f(27-5) + 1 (加上最后這一枚硬幣5）隆檀；如果 aK 是7，f(27)應(yīng)該是f(27-7) + 1 (加上最后這一枚硬幣7）粹湃。除此以外恐仑，沒有其他的可能了 。
需要求最少的硬幣數(shù)为鳄，所以： 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ù)計算，效率低下孤钦。下圖計算了三次f(20)：
解決方式：將計算結(jié)果保存下來歧斟，并改變計算順序。
動態(tài)規(guī)劃組成部分二：轉(zhuǎn)移方程
設(shè)狀態(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所需要的最少硬幣數(shù)：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]都已經(jīng)得到結(jié)果了。
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步。與遞歸算法相比庸蔼，沒有任何重復(fù)計算解总。算法時間復(fù)雜度（即需要進行的步數(shù)）： 面額數(shù)x硬幣種類。這里是27x3姐仅。
代碼如下：
def coin_change(coins, amount):
"""
換零錢動態(tài)規(guī)劃算法
:param coins: 零錢種類整數(shù)列表
:param amount: 需要換的面值
:return: 最少換取的硬幣數(shù)
"""
MAX_VALUE = 1e15
states = [MAX_VALUE] * (amount+1) # 狀態(tài)數(shù)組初始化花枫，包含狀態(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]
小結(jié)
求最值型動態(tài)規(guī)劃萍嬉，動態(tài)規(guī)劃組成部分：
- 確定狀態(tài)
? 最后一步（最優(yōu)策略中使用的最后一枚硬幣aK）
? 化成子問題（最少的硬幣拼出更小的面值27-aK） - 轉(zhuǎn)移方程
? f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1} - 初始條件和邊界情況
? f[0] = 0
? 如果不能拼出Y乌昔，f[Y]=正無窮 - 計算順序
? f[0], f[1], f[2], …
例2：不同的路徑數(shù)——計數(shù)型動態(tài)規(guī)劃
題目描述：
給定m行n列的網(wǎng)格隙疚，有一個機器人從左上角(0,0)出發(fā)壤追，每一步可以向下 或者向右走一步，問有多少種不同的方式走到右下角供屉。
組成部分一：確定狀態(tài)
最后一步：無論機器人用何種方式到達右下角行冰，總有最后挪動的一步：向右或者向下溺蕉。右下角坐標設(shè)為(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)肛走。問題轉(zhuǎn)化為漓雅，機器人有多少種方式從左上角走到(m-2, n-1)和(m-1, n-2)。原題要求有多少種方式從左上角走到(m-1, n-1)朽色。
狀態(tài)：設(shè) f[i][j] 為機器人有多少種方式從左上角走到(i, j)邻吞。
組成部分二：轉(zhuǎn)移方程
組成部分三：初始條件和邊界情況
- 初始條件：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]
- 時間復(fù)雜度（計算步數(shù)）：O(MN)，空間復(fù)雜度（數(shù)組大猩液帧）：O(MN)
代碼如下：
def unique_paths(m, n):
"""
:param m: 網(wǎng)格行數(shù)
:param n: 網(wǎng)格列數(shù)
:return: 從左上角到右下角所有的路徑數(shù)
"""
states = [[0] * n] * m # 狀態(tài)數(shù)組
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)：設(shè) f[j] 表示青蛙能不能跳到石頭 j 饺鹃。
組成部分二：轉(zhuǎn)移方程
組成部分三：初始條件和邊界情況
初始條件：f[0] = True，因為青蛙一開始就在石頭0间雀。
組成部分四：計算順序
? 設(shè)f[j]表示青蛙能不能跳到石頭j
?
? 初始化 f[0]=True
? 計算 f[1], f[2], …, f[n-1]
? 答案是 f[n-1]
? 時間復(fù)雜度：O(N2)悔详，空間復(fù)雜度（數(shù)組大小）：O(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]
以上代碼時間復(fù)雜度為 O(N2)惹挟，一般會運行超時茄螃，但是也是需要掌握的。優(yōu)化后的代碼（時間復(fù)雜度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) # 每一步更新可以跳到的最遠距離下標
總結(jié)
四個組成部分：
- 確定狀態(tài)
? 研究最優(yōu)策略的最后一步
? 化為子問題 - 轉(zhuǎn)移方程
? 根據(jù)子問題定義直接得到 - 初始條件和邊界情況
? 細心用狱，考慮周全 - 計算順序
? 利用之前的計算結(jié)果
常見動態(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%)
