动态规划（Dynamic Programming，简称 DP）是求解最优化问题的一种策略。DP 算法可以通过将原问题分解为若干个子问题的求解，并将子问题的解缓存起来以避免重复计算来达到减少计算时间的目的。
应用场景
- 求解最大值、最小值等最优化问题；
- 求解可行性问题，如是否存在某种状态；
解题思路
- 定义状态：DP 算法中状态需要定义清楚，该状态的定义需要关联题目中数组、字符串等数据的长度和题目所求解的目标值。
- 找到状态转移方程：将大问题转化为子问题，设计转移方程即从子问题的最优解推导父问题的最优解，需要通过题目来逐步推导方程。
- 初始状态：需要事先定义一些初始状态，用于转移过程的第一步或更底层的状态。
代码实现
下面实现一个背包问题的 DP 算法：
def knapsack(weights: List[int], values: List[int], W: int) -> int:
"""
背包问题
:param weights: 商品重量列表
:param values: 商品价值列表
:param W: 背包重量上限
:return: 最大价值
"""
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(1, W+1):
if weights[i-1] <= w:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]]+values[i-1])
else:
dp[i][w] = dp[i-1][w]
return dp[n][W]
我们将状态定义为 dp[i][w]，表示前 i 个商品，使背包重量为 w 时的最大价值。转移方程为：
$$
dp[i][w] =
\begin{cases}
max(dp[i-1][w], \ dp[i-1][w-weights[i-1]]+values[i-1]), & weights[i-1] <= w \
dp[i-1][w], & weights[i-1] > w
\end{cases}
$$
其中第一行 dp[0][j] = 0 表示当没有商品可选时，背包的最大价值为 0；第一列 dp[i][0] = 0 表示背包没有容量时，最大价值也是 0。
我们可以进行一个简单的测试：
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 8
res = knapsack(weights, values, W)
print(res) # 13
接下来再看一个经典的例题，计算斐波那契数列第 N 项的值。
def fib(n: int) -> int:
"""
计算斐波那契数列第 n 项的值
:param n: 求解的项数
:return: 指定项数的数值
"""
dp = [0] * (n+1)
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
这里我们将状态定义为 dp[i]，表示斐波那契数列第 i 项的值。转移方程为：
$$
dp[i] = dp[i-1] + dp[i-2], \ i\geq 2
$$
初始状态为 dp[0], dp[1] 分别为 0 和 1。我们可以进行测试：
res = fib(7)
print(res) # 13
这样，我们就通过两个示例讲解了动态规划算法的定义、思路和代码实现。