按需抉择：若重续航/便携选DP1，需高性能/扩展性则选DP2
什么是「DP1」与「DP2」？
在动态规划（Dynamic Programming, DP）中，「DP1」和「DP2」并非标准术语，而是开发者对两类常见状态设计模式的代称，以下是典型定义： | 特征 | DP1 | DP2 | |---------------|------------------------------|------------------------------| | 状态维度 | 单层/线性状态（一维数组） | 多层/复合状态（二维及以上数组）| | 依赖关系 | 仅依赖前序有限个状态 | 依赖多维组合状态 | | 典型场景 | 简单递推、贪心+记忆化 | 复杂子问题分解（如区间/双序列）| | 空间复杂度| O(n) | O(n²) 或更高 | | 时间复杂度| 通常更低 | 可能更高，但减少重复计算 |
核心差异对比表
| 维度 | DP1 | DP2 |
|---|---|---|
| 状态表示 | dp[i]：单一变量 |
dp[i][j]：二元组/多元组 |
| 转移来源 | 单向链式（如 i-1 → i） |
网状交叉（如 i-1,j 和 i,j-1） |
| 适用问题 | 线性序列类（爬楼梯、打家劫舍） | 矩阵/树形结构（编辑距离、股票买卖） |
| 优势 | ✅ 低空间占用 ✅ 易调试 |
✅ 精准捕捉子问题关联 ✅ 避免冗余计算 |
| 劣势 | ❌ 难以处理跨维度依赖 | ❌ 空间开销大 ❌ 初始化复杂 |
| 经典案例 | Fibonacci数列、硬币找零 | 最长公共子序列、背包问题变种 |
选型决策树
📌 Step 1: 判断问题类型
- 选DP1若满足以下任一条件：
- 输入为单层线性结构（数组/链表）
- 当前状态只与紧邻的前驱状态相关
- 无需回溯路径（仅需最终结果）
- 选DP2若满足以下任一条件：
- 涉及二维区域操作（如矩阵范围查询）
- 存在交叉依赖（如两个序列同步操作）
- 需要记录完整路径信息
📌 Step 2: 评估资源限制
| 条件 | 推荐方案 | 风险提示 |
|---|---|---|
| 内存敏感（n>1e5） | DP1 | 可能因简化模型丢失关键信息 |
| CPU时间紧张 | DP2（预存中间态） | 注意避免不必要的状态扩展 |
| 需支持反向推导路径 | DP2 | 必须额外维护父指针数组 |
📌 Step 3: 验证可行性
尝试手动模拟小规模测试用例：
（图片来源网络，侵删）
# 例：计算grid[0][0]到右下角的最小路径和 # DP1尝试（失败）：无法区分上下左右移动方向 # DP2实现（成功）：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
实战案例对比
Case A: 爬楼梯变种（仅限跳1或2步）→ 适用DP1
def climbStairs(n):
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]
优势：空间可压缩至O(1)，只需保存最近两次结果。
Case B: 编辑距离（允许插入/删除/替换）→ 必须用DP2
def minDistance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0](n+1) for _ in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i==0: dp[i][j] = j # 全插入
elif j==0: dp[i][j] = i # 全删除
else:
dp[i][j] = min(
dp[i-1][j] +1, # 删除
dp[i][j-1] +1, # 插入
dp[i-1][j-1] + (0 if word1[i-1]==word2[j-1] else 1) # 替换/匹配
)
return dp[m][n]
关键点：每个dp[i][j]需要同时参考左侧、上方、左上方三个状态。
相关问题与解答
Q1: 如果误将本该用DP2的问题强行套用DP1会怎样？
A：会导致状态丢失关键信息，例如编辑距离问题若只用一维数组，无法区分"来自上方"还是"来自左方"的操作路径，导致计算结果错误。
Q2: 有没有折中方案降低DP2的空间消耗？
A：可采用滚动数组技巧，对于很多DP2问题（如棋盘路径计数），发现dp[i][j]实际上只依赖于上一行的数据，因此可以将二维数组压缩为两行交替使用，将空间复杂度从O(mn)降至O(
（图片来源网络，侵删）
（图片来源网络，侵删）
