动态规划 (Dynamic Programming) 算法知识图谱

概述

动态规划是一种将复杂问题分解为更小子问题，通过存储子问题结果避免重复计算的算法思想。

核心概念

问题分类

类别	经典问题
**基础问题**	斐波那契、爬楼梯
**背包问题**	0/1背包、完全背包、多重背包
**序列问题**	LCS、LIS、编辑距离
**路径问题**	网格路径、障碍物
**股票问题**	买卖股票最佳时机
**区间DP**	合并石子、戳气球
**树形DP**	树的独立集、树的直径
**状态压缩DP**	旅行商、哈密顿路径
**DP优化**	空间优化、单调队列、斜率优化

解题步骤

[!abstract] DP 解题四步法

1. 确定状态 - 最后一步是什么？最优子结构
2. 转移方程 - dp[i] = f(dp[i-1], dp[i-2], ...)
3. 初始条件 - dp[0], dp[1] 等边界值
4. 计算顺序 - 从小到大、避免重复计算

适用条件

条件	说明
最优子结构	全局最优包含局部最优
无后效性	当前状态不受后续决策影响
重叠子问题	子问题会被多次求解

时间复杂度

维度	复杂度
状态数	O(n) - O(2^n)
转移数	O(1) - O(n)
总复杂度	状态 × 转移

---

最后更新: 2024-01-15