动态规划基础知识速览

一、面试常考点

把“重复子问题”结果缓存起来，用空间换时间。

状态定义、状态转移方程、初始化。

为什么能用 DP、是否有后效性、能否做状态压缩。

1. 定义 dp[i] / dp[i][j] 的语义
2. 找最后一步，写转移
3. 给边界初值
4. 选择遍历顺序
5. 考虑能否降维

如爬楼梯、打家劫舍、最小花费爬楼梯。

0-1 背包、完全背包、多重背包。

LIS、LCS、编辑距离。

回文、合并类问题。

股票买卖、冷冻期、手续费。

我会把「动态规划」分成三层来讲：先讲核心概念和它解决的问题，再讲一个高频场景与实现思路，最后补充常见坑点和优化方向。这样既能回答基础问题，也能接住面试官追问。

如果展开讲，我会按“定义 -> 原理 -> 场景 -> 取舍”四步回答。先说明「动态规划」解决的核心问题和边界；再讲 1 到 2 个关键机制，解释为什么这样设计；然后结合一个真实业务场景说明如何落地；最后补充常见坑点、性能或稳定性优化，以及与相近方案的取舍标准。

这样回答的好处是：既有原理深度，也有工程落地感，面试官继续追问到实现细节时也能自然展开。