动态规划（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]]
'''
