动态规划详解
什么是动态规划?
动态规划（DP）是一种通过将复杂问题分解为更小、更简单的子问题来解决问题的算法思想。这些子问题通常是重叠的，也就是说，在解决原始问题的过程中，它们会被多次重复计算。
动态规划的两个关键特性是：
- 最优子结构 (Optimal Substructure)：问题的最优解可以由其子问题的最优解构造而成。
- 重叠子问题 (Overlapping Subproblems)：一个问题可以被分解为若干个子问题，而这些子问题会多次重复出现。
为了避免重复计算，动态规划会存储这些子问题的解。主要有两种实现方式：
- 记忆化 (Memoization)：自顶向下的方法。我们从原始问题开始，通过递归解决子问题。每当解决一个子问题时，我们都将其结果存储起来，以便下次需要时可以直接使用，而不是重新计算。
- 制表法 (Tabulation)：自底向上的方法。我们从最简单的子问题开始，迭代地解决越来越复杂的问题，直到解决整个原始问题。我们通常使用一个表格（如数组或矩阵）来存储子问题的解。
示例1：斐波那契数列
斐波那契数列是一个经典的例子，用于说明动态规划。数列的定义如下：
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n > 1
1. 朴素递归解法
def fib_naive(n): if n <= 1: return n return fib_naive(n - 1) + fib_naive(n - 2)# 尝试计算一个较大的数，会发现速度非常慢# print(fib_naive(40)) # 这会花费很长时间！# 输出计算时间import timestart_time = time.time()fib_naive(10)end_time = time.time()elapsed_time = end_time - start_timeprint(f\"Elapsed time: {elapsed_time} seconds\")Elapsed time: 0.0 secondsstart_time = time.time()fib_naive(35)end_time = time.time()elapsed_time = end_time - start_timeprint(f\"Elapsed time: {elapsed_time} seconds\")Elapsed time: 0.8101024627685547 seconds上面的解法存在严重性能问题。例如，在计算 fib_naive(5) 时，fib_naive(3) 会被计算2次，fib_naive(2) 会被计算3次。这导致了指数级的时间复杂度 O(2^n)，因为存在大量的重叠子问题。
2. 记忆化 (自顶向下)
memo = {}def fib_memo(n): if n in memo: return memo[n] if n <= 1: return n result = fib_memo(n - 1) + fib_memo(n - 2) memo[n] = result return resultstart_time = time.time()fib_memo(10)end_time = time.time()elapsed_time = end_time - start_timeprint(f\"Elapsed time: {elapsed_time} seconds\")Elapsed time: 0.0 secondsstart_time = time.time()fib_memo(35)end_time = time.time()elapsed_time = end_time - start_timeprint(f\"Elapsed time: {elapsed_time} seconds\")Elapsed time: 0.0 seconds通过使用一个字典 memo 来存储已经计算过的斐波那契数，我们避免了重复计算。每个斐波那契数 F(i) (从 0 到 n) 只会被计算一次。因此，时间复杂度被优化到了 O(n)，空间复杂度为 O(n)（用于存储递归栈和备忘录）。
3. 制表法 (自底向上)
def fib_tab(n): if n <= 1: return n # 创建一个表来存储斐波那契数 table = [0] * (n + 1) table[1] = 1 # 从底向上填充表 for i in range(2, n + 1): table[i] = table[i - 1] + table[i - 2] return table[n]start_time = time.time()fib_tab(35)end_time = time.time()elapsed_time = end_time - start_timeprint(f\"Elapsed time: {elapsed_time} seconds\")Elapsed time: 0.0 seconds制表法直接从 F(2) 开始，迭代计算直到 F(n)。这种方法没有使用递归。时间复杂度同样是 O(n)，空间复杂度也是 O(n)（用于存储表格）。
对于斐波那契问题，我们还可以进一步优化空间，因为计算 F(i) 只需要 F(i-1) 和 F(i-2) 的值。所以我们只需要存储前两个值即可，可以将空间复杂度降至 O(1)。
示例2：0/1 背包问题
问题描述：
你有一个容量为 W 的背包，以及 n 个物品。每个物品都有自己的重量 weight[i] 和价值 value[i]。
你的目标是决定将哪些物品放入背包，使得在不超过背包总容量的前提下，包内物品的总价值最大。
对于每个物品，你要么不放，要么就完整地放进去（不能只放一部分），因此称为 0/1 背包问题。
制表法解法
我们可以使用一个二维数组 dp[i][w] 来解决这个问题，其中 dp[i][w] 表示：
从前 i 个物品中选择，放入容量为 w 的背包中所能获得的最大价值。
对于第 i 个物品，我们有两种选择：
- 不放入背包：那么最大价值就等于只考虑前
i-1个物品在容量为w的背包中的最大价值，即dp[i-1][w]。 - 放入背包（前提是
w >= weight[i-1]）：那么价值就是第i个物品的价值value[i-1]加上，在前i-1个物品中，放入容量为w - weight[i-1]的背包中的最大价值。即value[i-1] + dp[i-1][w - weight[i-1]]。
我们的状态转移方程就是：
dp[i][w] = max(dp[i-1][w], value[i-1] + dp[i-1][w - weight[i-1]])
def knapsack_01(weights, values, W): n = len(weights) # 创建一个 (n+1) x (W+1) 的二维数组，并初始化为 0 # dp[i][w] 表示从前 i 个物品中选择，放入容量为 w 的背包的最大价值 dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)] # 打印dp的大小 print(f\"dp的大小: {len(dp)} x {len(dp[0])}\") # 遍历所有物品 for i in range(1, n + 1): # 遍历所有可能的背包容量 for w in range(1, W + 1): # 当前物品的重量和价值 (注意索引是 i-1) current_weight = weights[i-1] current_value = values[i-1] # 如果当前物品的重量大于背包容量，则不能放入 if current_weight > w: dp[i][w] = dp[i-1][w] # 继承上一个状态 else: # 比较 放入 vs 不放入 put_in = current_value + dp[i-1][w - current_weight] not_put_in = dp[i-1][w] dp[i][w] = max(put_in, not_put_in) # 让二维数组打印成方格 print(\"+\" + \"---+\" * len(dp[0])) for row in dp: print(\"|\" + \" \".join(f\"{x:^3}\" for x in row) + \"|\") return dp[n][W] # 返回最终结果# 示例values = [6, 10]weights = [1, 2]W = 3max_value = knapsack_01(weights, values, W)print(f\"在容量为 {W} 的背包中，可以获得的最大价值是: {max_value}\") # 应该是 220 (物品2+物品3)dp的大小: 3 x 4+---+---+---+---+| 0 0 0 0 || 0 6 0 0 || 0 0 0 0 |+---+---+---+---+| 0 0 0 0 || 0 6 6 0 || 0 0 0 0 |+---+---+---+---+| 0 0 0 0 || 0 6 6 6 || 0 0 0 0 |+---+---+---+---+| 0 0 0 0 || 0 6 6 6 || 0 6 0 0 |+---+---+---+---+| 0 0 0 0 || 0 6 6 6 || 0 6 10 0 |+---+---+---+---+| 0 0 0 0 || 0 6 6 6 || 0 6 10 16 |在容量为 3 的背包中，可以获得的最大价值是: 16总结
动态规划是一种强大的技术，适用于具有最优子结构和重叠子问题特性的问题。
解决DP问题的步骤通常是：
- 定义状态：明确
dp[i]或dp[i][j]代表什么。这是最关键的一步。 - 找到状态转移方程：推导出
dp[i]是如何由之前的状态（如dp[i-1]）计算出来的。 - 确定初始条件：定义好
dp[0]或其他边界条件。
代码链接：https://github.com/zhouruiliangxian/Awesome-demo/tree/main/Data_Structures_and_Algorithms
