动态规划（Dynamic Programming， DP）算法采用递归的方式，将较复杂的原问题分解为较为简单的子问题，以求解原问题。

适用情况

一般情况下，我们能将问题抽象出来，并且问题满足无后效性，满足最优子结构，并且能明确的找出状态转移方程的话，就可以使用动态规划。

• 无后效性：子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响；
• 最优子结构：局部最优解能决定全局最优解，即问题能够分解成子问题来解决；
• 重叠子问题：子问题可能会重复出现，动态规划对每个子问题只解一次，并把解保存起来，方便后续直接调用，通常用一个二维矩阵（表格）来表示不同子问题的答案， 以实现更加高效的求解。；
• 状态转移：每种状态之间目标函数值的变化公式，从状态转移公式即可判断出最优子结构是否存在。

动态规划的实现

对于解空间规模较小的问题，动态规划算法可以利用递归算法实现，相比于单纯的递归算法，动态规划会将子问题的解存储起来，对重叠子问题不需要重新求解，加快了求解速度。

对于解空间规模较大的问题，递归次数过多会导致栈溢出。通常采用非递归算法来实现动态规划算法。

经典问题

斐波那契数列（待补充）

背包问题（待补充）

卡牌游戏问题

小a和小b玩一个游戏，有n张卡牌，每张上面有两个正整数x，y。取一张牌时，个人积分增加x，团队积分增加y。求小a，小b各取若干张牌，使得他们的个人积分相等，且团队积分最大。

用例描述：

输入：
4  # n=4 组数据
3 1  # x, y
2 2
1 4
1 4
输出：10  # 团队积分最大为10

设表示两人从前张卡片中进行抽取，且个人积分差（a-b）时，团队积分的最大值。因为两人的地位是平等的，我们可以假定，因为总是成立的。的取值分情况分析：
（1）当第张卡不需要抽取时，；
（2）当第张卡需要抽取时，要么是a抽取，要么是b抽取，我们假设相对于总是往减小两人积分差的方向变化。因此，。
因此转移方程为

其中，，初始边界条件为：

# 处理输入
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)  # 三种状态的最高得分
    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]]
'''