本博客内容来源于我在某企业担任算法助教期间的教学材料，将课堂使用的 PPT 转换为 PDF 后整理而成。
博客前面内容为讲义内容大纲
如果想仔细了解建议直接看最后的讲义原稿
动态规划基础 #
- 动态规划（Dynamic Programming, DP）是一种优化决策过程的算法思想，常用于最优子结构和重叠子问题的场景。
- 主要包括：
- 状态定义
- 状态转移方程
- 初始状态
- 最终结果计算
经典 DP 问题分类 #
线性 DP #
- 最长递增子序列（LIS）
- 斐波那契数列
- 打家劫舍
- 最小花费爬楼梯
网格 DP #
- 最小路径和
- 不同路径
- 最大正方形
背包问题 #
- 0/1 背包
- 完全背包
- 多重背包
状态机 DP #
- 股票买卖问题
- 最长公共子序列（LCS）
划分 DP #
- 戳气球
- 石子合并
区间 DP #
- 回文子串
- 合并石子
数位 DP #
- 统计特定数字的个数
- 数位拆分问题
状态压缩 DP #
- 旅行商问题（TSP）
- 集合覆盖问题
斐波那契数列引入 #
斐波那契数列： $$ F(n) = F(n - 1) + F(n - 2) $$
- 递归解法（时间复杂度 O(2^n)）
- 记忆化搜索（时间复杂度 O(n)）
- 动态规划（自底向上）（时间复杂度 O(n)）
- 矩阵快速幂（时间复杂度 O(log n)）
记忆化搜索 vs 动态规划 #
| 方法 | 适用情况 | 优点 | 缺点 |
|---|---|---|---|
| 记忆化搜索 | 递归问题 | 代码直观 | 可能栈溢出 |
| 动态规划 | 需要优化时间复杂度 | 避免重复计算 | 代码不一定直观 |
DP进阶 - 树上 DP #
- 换根 DP
- 树形背包
- 树的直径
课后练习题 #
-
最小花费爬楼梯（斐波那契进阶）
LeetCode 746 -
打家劫舍（经典 DP）
LeetCode 198 -
俄罗斯套娃信封问题（二维 LIS）
LeetCode 354 -
最长公共子序列（LCS）
LeetCode 1143
完整 PPT 预览 #
方式 1：腾讯文档在线预览 #
如果无法加载 PDF，请 点击这里打开腾讯文档。
直接预览：
方式 2：下载 PDF #
如果需要保存完整的 PDF 讲义，请点击下载： PDF 下载链接