动态规划的解题步骤是什么？
算法工程师第 7 / 15 题答题框架
参考思路：定义状态(明确含义)→转移方程→初始化与边界→遍历顺序→空间优化。用爬楼梯/打家劫舍演示五步法。
五个经典回答示范
回答一 · 思路口述版
「我解 DP 有固定五步：一定状态 dp[i] 的含义，二推转移方程，三定初始化，四定遍历顺序，五必要时空间优化。以打家劫舍为例：dp[i] 表示到第 i 家的最大金额，方程 dp[i]=max(dp[i-1], dp[i-2]+nums[i])，初始化 dp[0]=nums[0]，一维正序。」框架化让面试官看到可迁移的方法。
回答二 · 标准写法
以爬楼梯为例：dp[i] = dp[i-1] + dp[i-2]，dp[0]=1, dp[1]=1，一重循环。写完必做两件事：小用例代入验证初始值正确、说明滚动变量优化后空间 O(1)。进阶用 0-1 背包展示二维到一维的压缩——倒序遍历容量防止物品重复选取，这个细节是高频追问点。
回答三 · 进阶变体
三大类练透：线性 DP——打家劫舍、最长上升子序列（O(n²) 到贪心加二分的优化）；区间 DP——石子合并、回文类问题，遍历按长度从小到大；背包 DP——0-1 与完全背包的组合应用如零钱兑换、分割等和子集。每类讲一题的方程推导过程，比报题目数量有说服力。
回答四 · 边界与测试
DP 的错误集中在初始化与遍历顺序：初始化错一位全盘错；二维压缩一维时正序倒序选择错导致物品重复选；区间 DP 长度从 1 还是 2 开始要按题意。验证技巧：打印 dp 表对比手算的前几项，面试时主动提出打印调试是成熟习惯。
回答五 · 常见错误
错误一：背题解不知其所以然——状态含义被追问一句就塌。错误二：贪心与 DP 混淆——能用贪心的题（区间调度）硬上 DP，或反之。错误三：空间压缩后仍写二维遍历。点评：面试官问 DP 主要是看建模能力，讲清状态怎么来的比代码本身重要。
怎么练这道题
- 打开 模拟练习，选择「算法工程师」方向，限时 3 分钟作答本题。
- 对照上方答题框架，逐点检查：哪些要素没覆盖、哪里表达啰嗦。
- 用自己项目的真实经历替换框架中的占位内容，重讲一遍并录音回听。
这类题在真实面试中常被追问细节，
建议进入限时模式练一遍。