DP
DP
Created 2021.04.22 by William Yu; Last modified: 2023.11.01-V1.0.3
Contact: windmillyucong@163.com
Copyleft! 2023 William Yu. Some rights reserved.
References
- https://zhuanlan.zhihu.com/p/78220312
- https://zhuanlan.zhihu.com/p/265891102
- https://www.zhihu.com/question/39948290
Basic Concept
什么是动态规划?
-
简单来讲：
How should I explain dynamic programing to a 4-year-old?
Write down “1+1+1+1+1+1+1+1=” on a sheet of paper”
“what`s the answer?”
counting…
“Eight”
Write down another “1+” on the left
what about that
“Nine”
“how`d you know it was nine so fast”
“you just added one more”
“so you didn`t need to recount because you remembered there were eight!”
DP is just a fancy way to say remembering stuff to save time later
简述：
- 理解穷举与DP：
- 核心问题都是求最值
- 最简单方法是穷举，但暴力穷举效率非常低
- 可以使用动态规划优化穷举的前提条件：问题存在“重叠子问题”
- 动态规划能解的问题一定具有”最优子结构“，才能通过子问题的最值得到原问题的最值
- 能找到子问题之间的关联，列出正确的状态转移方程，才能正确是使用DP优化穷举
需要理解的词条：
- 重叠子问题
- 转移方程
- 状态压缩
思维框架
- 明确base case
- 明确状态，也就是原问题和子问题中会变化的变量
- 明确选择
- 定义dp数组/函数的含义
1
2
3
4
5
6
7
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in {状态1的所有可取值}：
for 状态2 in {状态2的所有可取值}：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2)
带备忘录的递归
- 耗时的原因是大量重复计算
- 因此尝试构造一个备忘录，算出某个子问题之后不急着返回，先记入备忘录
- 遇到一个子问题后先去备忘录里面查找，如果发现已经解决过这个问题，直接将答案拿出来用
- 一般使用数组，或者哈希表（字典）
- 算法复杂度降为$O(n)$
1
区别与联系
- 带备忘录的递归 和 迭代的动态规划 差不多
- 带备忘录的递归 自顶向下
- 动态规划 自底向上
- 备忘录即DP table
- 状态转移方式其实就是递推公式
- DP table的缩减过程称为状态压缩
状态压缩
- 如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据
复杂度计算
DP的状态为节点，节点数量 m DP的状态转移为边，边数量 n
DP的 时间复杂度 来自于两部分：
- 状态转移次数，即边的数量 m
- 单个 状态转移 的 计算复杂度 k
- 总体的时间复杂度 为 n x k
Contact
Feel free to contact me windmillyucong@163.com anytime for anything.
