动态规划方法论

⚡ 30 秒速记

• 动态规划把原问题表示为可复用的子问题状态，并按依赖顺序保存最优答案
• 状态定义必须包含决定未来选择所需的全部信息，转移只能读取已经正确计算的状态
• 先写 base case、非法状态和遍历方向，再写状态转移；初始化值必须匹配求最大或最小的语义

动态规划的核心，是把原问题拆成可复用的子问题状态，并按照依赖顺序保存各状态的最优结果。 状态要包含后续决策真正需要的信息，否则转移时会缺条件；同时，转移只能读取已经正确计算出的状态。我一般会先确定边界、非法状态和遍历方向，再落状态转移，因为初始化必须和求最大值或最小值的语义一致。面对陌生题时，从具体状态之间的关系入手，通常比直接套抽象公式更稳妥。

动态规划是算法面试中的一个“大IP”，同时也是很多同学的心头痛。本节致力于用舒服的姿势帮助大家克服这块心病，因此开篇不能急于怼知识点，要先讲讲方法。

在笔者看来，对于动态规划的学习，最重要的是找到一个正确的学习切入点：如果你是一个对相关理论一无所知的初学者，自然不能急于一上来就生吞“模型”、“状态转移方程”等高端概念——大家谨记，动态规划是一种思想，所谓思想，就是非常好用，好用到爆的套路。我们学习一种思想，重要的是建立起对它的感性认知，而不是反复咀嚼那些对现在的你来说还非常生硬的文字概念——从抽象去理解抽象是意淫，从具体去理解抽象才是学习。

首先带大家一起解决一个实际的问题，然后逐步复盘问题的解决方案，最后从解决方案中提取出动态规划相关的概念、模型和技巧，实现对号入座。

从前面一系列章节的学习反馈中，笔者观察到一部分同学的阅读习惯非常“薄情”——打开小册只为做题，做完就溜，讲解部分基本是不看的。

这里想要提醒大家的是，题目本身不仅仅是命题点，更是素材、是教具，大家最终要关注到的还是题目背后的思想和方法。因此希望同学们能多给自己一点时间、多一些耐心去反刍和吸收知识。

💬 面试官追问

• 新人在评审会上先背出“最优子结构、状态转移方程”，却说不清爬楼梯页面里状态代表什么，你会怎样判断他的掌握程度？

  这说明他记住了抽象术语，但还没有建立可用于解题的具体认知。应让他先用一个实际目标解释状态、选择和结果，再从解法中提炼模型；若脱离题目仍只能复述定义，面对约束变化时很容易机械套公式。

• 团队准备给训练平台新增动态规划入门页，页面空间只能保留一道完整例题或一页概念速查，你会选哪种内容结构？

  应优先保留一道从实际问题、解法复盘到概念提炼的完整例题，让读者看到抽象术语如何从具体决策中产生。概念速查可以作为索引补充，但不应成为首次入口；只给结论会降低篇幅，却难以检验学习者是否真正理解。

• 课程负责人要求第一屏直接展示通用 dp 模板和状态转移方程，目标用户却是从未接触动态规划的前端开发者，你会接受吗？

  不建议把抽象模板作为唯一入口，因为目标用户缺少把符号映射到问题过程的经验。更稳妥的安排是先解决具体题目，再复盘状态与转移如何出现，最后对号入座到术语；代价是前置篇幅更长，但能减少生吞模型造成的误用。

• 培训页面完成率正常，但学员换一道相似题就无法定义状态，日志显示多数人做完题后跳过讲解，你会怎样定位故障？

  故障更像学习流程只完成了“拿到答案”，没有完成对解法的反刍和抽象。应检查页面是否强制或引导学员解释状态含义、决策关系与推导过程，而不只校验代码结果；若仍以题目通过数衡量效果，完成率会掩盖迁移能力不足。

• 面试准备只剩两天，候选人主张刷更多题，导师主张停下来复盘少量题目的方法论，你会怎样取舍？

  应保留做题，但把重心放在复盘少量代表题，明确每道题背后的状态、关系和解题思想。题目既是命题点也是理解方法的教具，只追求数量容易形成见题背答案的依赖；短期题量可能减少，但更有利于迁移到未见题型。