序言 ​

关于本书 ​

这是《LeetCode 算法通关之路》系列的第三册——动态规划精通篇。

动态规划（DP）是算法面试的重中之重，也是很多程序员的"噩梦"。本书将带你系统攻克这座大山。

前置要求 ​

学习本书前，你需要具备：

• ✅ 扎实的递归思维（第二册第一部分）
• ✅ 熟悉回溯算法的基本框架（第二册第十部分）
• ✅ 理解时间复杂度和空间复杂度
• ✅ 基本的数学思维

如果递归思维不够扎实，强烈建议先学习第二册的"递归思维训练"章节。

为什么动态规划难？ ​

动态规划难在两点：

1. 状态定义：如何定义子问题，需要大量练习才能形成直觉
2. 状态转移：如何从小问题的解推导大问题的解

本书的核心目标就是帮你建立这两方面的能力。

本书内容 ​

本书覆盖 13 类动态规划变体：

学习方法论 ​

动态规划五步法 ​

每道 DP 题目，按以下步骤思考：

1. 确定状态：dp[i] 或 dp[i][j] 表示什么？
2. 写出转移：dp[i] 如何从 dp[j] (j < i) 推导？
3. 确定边界：dp[0] 或 dp[0][0] 是什么？
4. 确定顺序：遍历顺序如何保证子问题已解决？
5. 优化空间：能否降维？能否滚动数组？

从记忆化搜索入手 ​

如果直接写递推困难，可以：

1. 先写暴力递归
2. 添加备忘录（记忆化搜索）
3. 改写为递推形式

本书第二部分"记忆化搜索与递推"专门讲解这个过程。

本书在丛书中的位置 ​

第一册 → 第二册 → [第三册] → 第四册 → 第五册 → 第六册
数据结构   算法技巧   动态规划   图论搜索   高级结构   算法竞赛
  基础       篇       精通篇     篇        篇        实战篇

与相邻册次的关系 ​

← 前置：第二册《算法技巧篇》

• 递归是 DP 的思想基础
• 回溯是 DP 的暴力版本

→ 后续：第四册《图论与搜索篇》

• 图上也有 DP 问题（如最短路）
• 搜索与 DP 常结合使用

→ 关联：第六册《算法竞赛实战篇》

• 博弈型 DP 的进阶内容在第六册

学习建议 ​

1. 打好基础：前六部分是核心，必须吃透
2. 大量练习：DP 没有捷径，只有多练
3. 分类总结：每类 DP 都有固定套路，要善于归纳
4. 画图辅助：状态转移可以画图帮助理解

开始学习 ​

动态规划是算法学习的分水岭。

跨过这道坎，你将进入算法的新境界。

祝学习愉快！