力扣总结 常见算法（七）：动态规划
目录
动态规划是一种特殊的递归，适用于有重叠子问题的场景。
存在大量重叠的子问题时，普通的递归写法会重复计算这些子问题，浪费大量时间。 动态规划会保存所有子问题的结果，避免重复计算。
动态规划也有递归和非递归两种形式。递归形式的动态规划也叫记忆化递归， 非递归形式即是保存中间结果的递推。
python 在递归函数上加一个 @lru_cache(None) 的装饰器即可实现记忆化递归。 非递归形式一般初始化一个 k（动态参数个数）维的数组保存子问题的结果。
递归层数太多时容易爆栈，用非递归形式更好。 但有时所求问题只会用到稀疏的子问题，此时用递归形式更节省时间。
1 单推 dp
有的问题结果完全依赖于几个初始值和递推式：
- 有时能用简洁的函数表达式直接表达，比如组合数
- 有的递推式可以用矩阵快速幂优化时间
1.1 基础
1.2 进阶
1.3 挑战
- 0552 学生出勤记录 II
2 线性 dp
2.1 基础
2.2 进阶
2.3 挑战
3 线性 dp 典型问题
3.1 子数组/子串
3.2 子序列
3.3 多串 dp
3.4 打家劫舍系列
3.5 股票系列
- 0121 买卖股票的最佳时机
- 0122 买卖股票的最佳时机 II
- 0123 买卖股票的最佳时机 III
- 0188 买卖股票的最佳时机 IV
- 0309 最佳买卖股票时机含冷冻期
- 0714 买卖股票的最佳时机含手续费
3.6 背包 dp
4 矩阵 dp
4.1 基础
4.2 进阶
4.3 挑战
5 区间 DP
5.1 基础
5.2 进阶
5.3 挑战
6 哈希 dp
有时需要递推的不是单纯的值，而是集合/计数器
6.1 基础
6.2 进阶
- 0241 为运算表达式设计优先级
6.3 挑战
- 0446 等差数列划分 II - 子序列
7 状压 dp
8 数位 dp
9 图上 dp
- 0126 单词接龙 II
10 博弈 dp
11 dp 优化
11.1 dp+上下界
- 0808 分汤
11.2 dp+前缀和
11.3 dp+二分
- 0514 自由之路
11.4 dp+构造
11.4 dp+折半搜索
- 0805 数组的均值分割