动态规划题解
动态规划是面试中最具区分度的算法类型。
刷题顺序建议：
- 线性 DP（爬楼梯、打家劫舍）
- 股票问题系列（状态机 DP）
- 背包问题（01 背包、完全背包）
- 子序列问题（LCS、LIS、编辑距离）
- 区间 DP（石子合并、回文串）
- 状态压缩 DP（旅行商问题变体）
核心方法论：
- 明确「状态」含义（dp[i] 代表什么）
- 推导「转移方程」（dp[i] 如何从之前状态得到）
- 确定「初始条件」与「边界」
- 空间优化（滚动数组、常数空间）
相关文章：
动态规划必刷12题：从爬楼梯到股票问题
精选LeetCode动态规划领域12道必刷题目，覆盖线性DP、状态机DP、背包问题与区间DP四大类型，详解状态定义与转移方程的推导过程。