清华动态规划专题课2025

动态规划是那种「听课时觉得懂了，做题时发现自己没懂」的典型内容。状态定义写不出来，转移方程推不下去，边界条件一改就错，最后靠背题解混过去——如果你正处在这样的阶段，这套清华的动态规划专题课值得当作一次系统补课，而不是又一轮「刷完就忘」。

先确认你缺的到底是哪一块

动态规划的知识缺口通常不是单一的一处，先对照一下自己卡在哪个环节。

• 知道要用 DP，但写不出状态：不清楚该把什么量当作阶段的描述，维度一多就乱。
• 状态能定义，转移方程列不出来：找不到子问题之间的依赖关系，或者依赖关系带环。
• 方程写得对，实现总出错：初始化、遍历顺序、滚动数组、记忆化搜索的边界理不清。
• 经典模型见过但记不牢：背包、区间、树形、状压、数位这几类题目换层皮就不认识了。
• 会做题但不会优化：时间复杂度降不下来，不知道什么时候可以用单调队列、斜率优化、四边形不等式。

这套课的内容范围覆盖了基本概念与原理、常见问题与解法、算法竞赛中的应用，以及动态规划在计算机科学其他方向的使用。也就是说，它不只服务竞赛刷题，也包括字符串编辑距离、序列比对、资源分配这类工程和理论场景里的 DP 建模。按上面的清单自查，缺哪块就重点看哪块，不必从头平推。

这门课重点解决三个「说不清」

第一个是「状态为什么这么定义」。动态规划最难的从来不是写代码，而是从问题描述里抽象出阶段和状态。课程从原理层面讲这件事，比直接给模板更有用，因为题目一变形，模板就失效了。

第二个是「转移方程怎么推」。常见问题部分按模型分类讲，把同类问题的推导思路摊开，让你看到方程是从子问题结构里长出来的，而不是凭空出现的。

第三个是「优化什么时候用得上」。朴素 DP 往往能过样例过不了数据，优化技巧属于知道就会、不知道就干瞪眼的那类知识。这部分建议结合竞赛例题看，脱离题目单独记技巧意义不大。

配套练习该怎么用

课程配有练习题和案例，正确的用法不是看完一节做一节。更有效的做法是：看完一个模型的讲解后，先把例题关掉自己重推一遍状态和方程，写出来再对照；然后再做同模型的变式题，检验自己是真的掌握了结构，还是只记住了那道题。

另外建议准备一个错题记录，只记两件事：这道题的状态是什么、我当初为什么没想到。积累十几道之后，你会发现自己卡住的往往是同一类结构问题，而不是零散的知识点。

看完应该能回答的问题

• 拿到一道题，你凭什么判断它适合用动态规划而不是贪心或搜索？
• 给你一个具体问题，你能写出状态定义，并说明它满足无后效性吗？
• 记忆化搜索和递推写法各自适合什么场景，什么时候必须用其中一种？
• 背包问题的几种变形之间，区别到底在遍历顺序还是状态维度上？
• 面对一维线性 DP，你能判断出它能不能优化、该用哪种优化吗？

如果这些问题你现在只能答出一半，说明还有明确的补课空间；如果大部分能答上来，这套课更适合当作查漏，挑薄弱章节看即可。动态规划没有速成，但方向对了，每道题都在积累结构感，而不是在攒题解。