動(dòng)態(tài)規(guī)劃（Dynamic Programming， DP）算法采用遞歸的方式，將較復(fù)雜的原問(wèn)題分解為較為簡(jiǎn)單的子問(wèn)題，以求解原問(wèn)題。

適用情況

一般情況下，我們能將問(wèn)題抽象出來(lái)，并且問(wèn)題滿(mǎn)足無(wú)后效性，滿(mǎn)足最優(yōu)子結(jié)構(gòu)，并且能明確的找出狀態(tài)轉(zhuǎn)移方程的話(huà)，就可以使用動(dòng)態(tài)規(guī)劃。

• 無(wú)后效性：子問(wèn)題的解一旦確定，就不再改變，不受在這之后、包含它的更大的問(wèn)題的求解決策影響；
• 最優(yōu)子結(jié)構(gòu)：局部最優(yōu)解能決定全局最優(yōu)解，即問(wèn)題能夠分解成子問(wèn)題來(lái)解決；
• 重疊子問(wèn)題：子問(wèn)題可能會(huì)重復(fù)出現(xiàn)，動(dòng)態(tài)規(guī)劃對(duì)每個(gè)子問(wèn)題只解一次，并把解保存起來(lái)，方便后續(xù)直接調(diào)用，通常用一個(gè)二維矩陣（表格）來(lái)表示不同子問(wèn)題的答案， 以實(shí)現(xiàn)更加高效的求解。；
• 狀態(tài)轉(zhuǎn)移：每種狀態(tài)之間目標(biāo)函數(shù)值的變化公式，從狀態(tài)轉(zhuǎn)移公式即可判斷出最優(yōu)子結(jié)構(gòu)是否存在。

動(dòng)態(tài)規(guī)劃的實(shí)現(xiàn)

對(duì)于解空間規(guī)模較小的問(wèn)題，動(dòng)態(tài)規(guī)劃算法可以利用遞歸算法實(shí)現(xiàn)，相比于單純的遞歸算法，動(dòng)態(tài)規(guī)劃會(huì)將子問(wèn)題的解存儲(chǔ)起來(lái)，對(duì)重疊子問(wèn)題不需要重新求解，加快了求解速度。

對(duì)于解空間規(guī)模較大的問(wèn)題，遞歸次數(shù)過(guò)多會(huì)導(dǎo)致棧溢出。通常采用非遞歸算法來(lái)實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法。

經(jīng)典問(wèn)題

斐波那契數(shù)列（待補(bǔ)充）

背包問(wèn)題（待補(bǔ)充）

卡牌游戲問(wèn)題

小a和小b玩一個(gè)游戲，有n張卡牌，每張上面有兩個(gè)正整數(shù)x，y。取一張牌時(shí)，個(gè)人積分增加x，團(tuán)隊(duì)積分增加y。求小a，小b各取若干張牌，使得他們的個(gè)人積分相等，且團(tuán)隊(duì)積分最大。

用例描述：

輸入：
4  # n=4 組數(shù)據(jù)
3 1  # x, y
2 2
1 4
1 4
輸出：10  # 團(tuán)隊(duì)積分最大為10

設(shè)表示兩人從前張卡片中進(jìn)行抽取，且個(gè)人積分差（a-b）時(shí)，團(tuán)隊(duì)積分的最大值。因?yàn)閮扇说牡匚皇瞧降鹊?，我們可以假?img class="math-inline" src="https://math.jianshu.com/math?formula=j%5Cgeq%200" alt="j\geq 0" mathimg="1">，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=d_%7Bi%2Cj%7D%3Dd_%7Bi%2C-j%7D" alt="d_{i,j}=d_{i,-j}" mathimg="1">總是成立的。的取值分情況分析：
（1）當(dāng)?shù)?img class="math-inline" src="https://math.jianshu.com/math?formula=i" alt="i" mathimg="1">張卡不需要抽取時(shí)，；
（2）當(dāng)?shù)?img class="math-inline" src="https://math.jianshu.com/math?formula=i" alt="i" mathimg="1">張卡需要抽取時(shí)，要么是a抽取，要么是b抽取，我們假設(shè)相對(duì)于總是往減小兩人積分差的方向變化。因此，。
因此轉(zhuǎn)移方程為

其中，，初始邊界條件為：

# 處理輸入
n = int(input())
x, y = [], []
for i in range(n):
    _x, _y = list(map(int, input().split()))
    x.append(_x)
    y.append(_y)

# 初始化
mx = max(x)  # 獲取最大值，作為差的邊界
dp = [[0] * (mx+1) for _ in range(n+1)]  # 初始化dp

# 邊界條件
dp[1][x[0]] = max(dp[1][x[0]], y[0])

for i in range(1, n):
    for j in range(mx+1):
        tmp1, tmp2 = 0, 0            
        tmp1 = dp[i-1][abs(j-x[i])] + y[i]
                
        if j + x[i] <= mx:                
            tmp2 = dp[i-1][j+x[i]] + y[i]

        dp[i][j] = max(dp[i-1][j], tmp1, tmp2)  # 三種狀態(tài)的最高得分
    print(dp[i])

print(dp[n-1][0])
'''
10
'''
print(dp)
'''
[[0, 0, 0, 0], 
[0, 0, 2, 0], 
[0, 3, 2, 0], 
[7, 6, 7, 6], 
[10, 11, 10, 11]]
'''