动态规划（Dynamic Programming, DP）是一种通过将问题分解为更小的子问题，并存储这些子问题的解来避免重复计算的方法。它通常用于解决具有重叠子问题和最优子结构性质的问题。
1. 基本概念
动态规划的核心思想是将复杂问题分解为简单的子问题，并通过存储这些子问题的解来提高效率。动态规划通常使用一个表格（数组或字典）来存储子问题的解，以避免重复计算。
2. 示例：斐波那契数列
斐波那契数列是一个经典的动态规划问题。我们可以通过自底向上的方式实现它，从而避免递归中的大量重复计算。
实现代码
def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
# 创建一个数组来存储子问题的解
dp = [0] * (n + 1)
dp[1] = 1
# 填充数组
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# 测试
print(fibonacci(6)) # 输出 8
在这个例子中，我们使用一个数组 dp 来存储从 0 到 n 的斐波那契数。通过迭代填充这个数组，我们避免了递归中的重复计算。
3. 示例：背包问题
背包问题是另一个经典的动态规划问题。假设你有一个容量为 W 的背包和 n 个物品，每个物品有一个重量和一个价值。目标是选择一些物品放入背包，使得总价值最大且总重量不超过 W。
实现代码
def knapsack(weights, values, W):
n = len(weights)
# 创建一个二维数组来存储子问题的解
dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
# 填充数组
for i in range(1, n + 1):
for w in range(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]
# 测试
weights = [1, 2, 3]
values = [6, 10, 12]
W = 5
print(knapsack(weights, values, W)) # 输出 22
在这个例子中，我们使用一个二维数组 dp 来存储子问题的解。dp[i][w] 表示前 i 个物品在容量为 w 的背包中的最大价值。通过迭代填充这个数组，我们可以找到最优解。
4. 示例：最长公共子序列（LCS）
最长公共子序列是另一个常见的动态规划问题。给定两个字符串，找到它们的最长公共子序列的长度。
实现代码
def longest_common_subsequence(X, Y):
m = len(X)
n = len(Y)
# 创建一个二维数组来存储子问题的解
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
# 填充数组
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
# 测试
X = "AGGTAB"
Y = "GXTXAYB"
print(longest_common_subsequence(X, Y)) # 输出 4
在这个例子中，我们使用一个二维数组 dp 来存储子问题的解。dp[i][j] 表示字符串 X 的前 i 个字符和字符串 Y 的前 j 个字符的最长公共子序列的长度。通过迭代填充这个数组，我们可以找到最长公共子序列的长度。
5. 注意事项
- 状态定义：明确定义子问题的状态，这是动态规划的关键。
- 状态转移方程：找出子问题之间的关系，即状态转移方程。
- 初始条件：确定边界条件，通常是最小的子问题。
- 空间优化：有时可以通过滚动数组等技术来优化空间复杂度。
通过这些示例和注意事项，你可以在 Python 中有效地实现和使用动态规划来解决各种复杂的问题。
