动态规划（Dynamic Programming, DP）是一种通过**将复杂问题分解为重叠子问题**，并**保存子问题的解（记忆化）**来避免重复计算、从而高效求解最优化问题的算法设计范式。它适用于满足以下两个关键性质的问题： - **最优子结构（Optimal Substructure）**：问题的最优解包含其子问题的最优解； - **重叠子问题（Overlapping Subproblems）**：在递归求解过程中，同一子问题被多次重复计算。 ⚠️ 注意：动态规划 ≠ 递归 + memorization（虽然这是常见实现方式），更核心的是**状态定义 + 状态转移方程 + 边界条件 + 决策顺序（自底向上或自顶向下）**。 --- ### ✅ 何时使用动态规划？（典型场景判断） | 场景特征 | 示例问题 | |----------|-----------| | 求“最多/最少/最长/最短/方案数”等极值或计数类问题 | 最长上升子序列（LIS）、背包问题、编辑距离、路径最小和、股票买卖最佳时机（含冷冻期/手续费） | | 存在明显阶段性和决策依赖（当前决策依赖前若干状态） | 爬楼梯（每次1或2步）、打家劫舍（不能偷相邻房）、分割回文串 | | 可形式化定义清晰的状态 `dp[i]` 或 `dp[i][j]`，且能写出明确转移方程 | `dp[i] = max(dp[i-1], dp[i-2] + nums[i])`（打家劫舍） | | 暴力搜索/递归超时（指数级），但状态空间有限（如 `O(n²)` 或 `O(n·W)`） | `n ≤ 5000`, `W ≤ 10⁴` 等中等规模约束下，DP 往往可过 | ❌ 不适用场景： - 无重叠子问题（如归并排序的子问题互不重叠 → 分治即可）； - 状态空间爆炸且无法压缩（如 `dp[mask][i]` 中 `mask` 是 2^30 → 不可行）； - 最优子结构不成立（如带全局约束的非局部优化问题，需用搜索+剪枝或贪心试探）。 --- ### 🧩 通用 Python 动态规划代码模板（含数据导入 & 预处理） 下面以经典的 **0-1 背包问题（Knapsack）** 为例，给出一个**工业级可扩展模板**，涵盖： - 数据导入（支持 CSV / 字典 / 列表输入） - 数据校验与预处理（类型、范围、空值） - DP 状态定义、初始化、状态转移（自底向上二维/空间优化一维） - 结果解码（不仅返回最大价值，还支持回溯路径） - 时间/空间复杂度注释 > 💡 为什么选背包？—— 它是 DP 的“Hello World”，兼具状态二维性、边界处理、路径还原、空间优化等全部要素。 ```python import csv import sys from typing import List, Tuple, Optional, Dict, Any import pandas as pd # ================== 1. 数据导入模块 ================== def load_knapsack_data( source: str | List[Dict[str, Any]] | None = None, file_path: str | None = None, weights: List[int] | None = None, values: List[int] | None = None, capacity: int | None = None ) -> Tuple[List[int], List[int], int]: """ 统一入口：支持多种方式加载背包数据 支持：CSV文件、字典列表、显式传入weights/values/capacity 返回: (weights, values, capacity) """ if file_path: # CSV格式：每行 weight,value （如：2,3） with open(file_path, 'r') as f: reader = csv.reader(f) rows = [row for row in reader if row] weights = [int(r[0]) for r in rows] values = [int(r[1]) for r in rows] assert len(weights) == len(values), "weight and value length mismatch" elif isinstance(source, list): # 字典列表: [{"weight":2,"value":3}, ...] weights = [item["weight"] for item in source] values = [item["value"] for item in source] elif weights and values and capacity: pass # 已直接提供 else: raise ValueError("Must specify one of: file_path, source(list), or (weights, values, capacity)") # 校验 assert all(w > 0 for w in weights), "All weights must be positive integers" assert all(v >= 0 for v in values), "All values must be non-negative integers" assert capacity > 0, "Capacity must be positive" return weights, values, capacity # ================== 2. DP 主体：0-1 背包（二维 + 路径还原）================== def knapsack_dp_2d( weights: List[int], values: List[int], capacity: int ) -> Tuple[int, List[int]]: """ 二维DP解法：dp[i][w] = 前i个物品在容量w下的最大价值 时间: O(n*W), 空间: O(n*W) 返回: (max_value, selected_indices) """ n = len(weights) # 初始化：dp[i][w] 表示前i个物品（i从0到n），容量w的最大价值 dp = [[0] * (capacity + 1) for _ in range(n + 1)] # 状态转移 for i in range(1, n + 1): for w in range(capacity + 1): # 不选第i-1个物品（索引从0开始） dp[i][w] = dp[i-1][w] # 选第i-1个物品（需容量足够） if weights[i-1] <= w: dp[i][w] = max( dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1] ) # 回溯找解（哪些物品被选中） selected = [] w = capacity for i in range(n, 0, -1): if dp[i][w] != dp[i-1][w]: # 说明第i-1个物品被选 selected.append(i-1) w -= weights[i-1] return dp[n][capacity], sorted(selected) # ================== 3. 空间优化版：一维DP（推荐日常使用）================== def knapsack_dp_1d( weights: List[int], values: List[int], capacity: int ) -> Tuple[int, List[int]]: """ 空间优化：dp[w] = 容量w下的最大价值（滚动数组） ⚠️ 注意：内层循环必须倒序！否则会重复使用同一物品（变成完全背包） 时间: O(n*W), 空间: O(W) 注：路径还原需额外记录 pre[w] 或二次DP，此处为简洁省略；实际项目建议用2D或存parent数组。 """ n = len(weights) dp = [0] * (capacity + 1) # 记录每个容量w下最后更新它的物品索引（用于路径还原） parent = [-1] * (capacity + 1) # parent[w] = 物品索引i，表示dp[w]由i更新而来 for i in range(n): # 倒序遍历容量，避免重复选择 for w in range(capacity, weights[i] - 1, -1): if dp[w] < dp[w - weights[i]] + values[i]: dp[w] = dp[w - weights[i]] + values[i] parent[w] = i # 回溯路径（从 capacity 开始） selected = [] w = capacity while w > 0 and parent[w] != -1: i = parent[w] selected.append(i) w -= weights[i] # 避免无限循环：跳过已计入的物品（注意：此简化版假设无重复贡献） parent[w] = -1 # 标记已访问（严格路径还原应建 predecessor matrix） return dp[capacity], sorted(set(selected)) # 去重并排序 # ================== 4. 使用示例与入口 ================== if __name__ == "__main__": # 方式1：硬编码 ws = [2, 1, 3, 2] vs = [3, 2, 4, 2] W = 5 # 方式2：从CSV读取（取消注释并准备 data.csv） # ws, vs, W = load_knapsack_data(file_path="data.csv") print("Weights:", ws) print("Values: ", vs) print("Capacity:", W) max_val, items = knapsack_dp_2d(ws, vs, W) print(f"\n✅ 2D DP Result:") print(f"Max Value = {max_val}") print(f"Selected Items (0-indexed): {items}") print(f"Selected Weights: {[ws[i] for i in items]}") print(f"Selected Values: {[vs[i] for i in items]}") max_val2, items2 = knapsack_dp_1d(ws, vs, W) print(f"\n✅ 1D DP Result:") print(f"Max Value = {max_val2}") print(f"Selected Items: {items2}") # ✅ 扩展提示：如何快速判断是否该用DP？ print("\n💡 When to use DP? Check these:") print(" ✔️ Optimization goal (max/min/count)?") print(" ✔️ Decisions depend on prior states (not just greedy choice)?") print(" ✔️ Same subproblem appears repeatedly? (e.g., fib(3) called many times)") print(" ❌ If 'no' to any above → consider greedy / DFS / BFS / math instead.") ``` --- ### 🔍 关键解释说明： | 模块 | 说明 | |------|------| | **`load_knapsack_data`** | 统一数据入口，解耦业务逻辑与算法，便于单元测试和生产配置（如从数据库、API、配置文件加载）；含健壮校验。 | | **`knapsack_dp_2d`** | 教学友好：状态含义清晰 (`dp[i][w]`)，易于理解转移逻辑；支持完美路径还原（回溯 `selected`）。适合调试、面试、小规模问题。 | | **`knapsack_dp_1d`** | 工业首选：空间从 `O(nW)` 降至 `O(W)`，常数更小；通过倒序循环保证0-1性质；`parent` 数组实现轻量路径还原。 | | **路径还原原理** | 利用 DP 表的“决策痕迹”：若 `dp[i][w] ≠ dp[i−1][w]`，说明第 `i−1` 个物品被选；逆向追踪即可得完整解集。 | | **时间复杂度** | `O(n × capacity)` —— 当 `capacity` 很大（如 `1e9`）时不可行 → 此时应考虑「值域DP」（以 value 为状态，min weight to achieve value v）或「分支限界」。 | --- ### 📌 进阶提醒（避坑指南）： - ✅ **初始化陷阱**：`dp[0][*] = 0`（0个物品价值为0），但某些问题需 `dp[0][0]=0, dp[0][w>0]=-inf`（强制必须装满）； - ✅ **滚动数组方向**：0-1背包→倒序；完全背包→正序； - ✅ **状态压缩技巧**：当 `n` 大 `W` 小 → 用 `dp[W]`；当 `W` 大 `value_sum` 小 → 用 `dp[value_sum]`（对背包变种）； - ✅ **打印DP表辅助调试**：`print('\n'.join(map(str, dp)))` 可直观验证转移是否符合预期。 ---