记忆化搜索
记忆化搜索是一种 DP 的实现方法。
相同点：
-
DP 中同一局部问题只计算一次——搜索的记忆化
-
不处理对答案没有贡献的情况——对应搜索的剪枝
不同点：
-
遍历顺序优化复杂度。
-
按数组顺序进行的 DP，经常可以配合一些优化技巧进一步降低复杂度。
“DP 是一种算法，一个工具，而非一种题型。这也是为什么有时候很难分辨一道题要用 DP 还是用贪心，因为你确实很难直接从题面判断要用什么工具。”
“DP 的核心在于设计状态。独立设计一个好的状态可能较为困难，但我们可以根据学过的通用状态进行拓展，得到当前的状态。”
数位 DP
经典数位 DP 的要素：求 l 到 r 之间的符合限制的数的个数（或求和），通常这个限制与数位有关。
数位 DP 的主要思想是，把大整数看成一个由 \(0 \sim 9\) 构成的整数序列而不是一个数。并采用序列 DP 的方式，从高位到低位一位一位地 DP。
我之前在 进阶动态规划学习笔记 中写到需要拼凑 + 预处理。实际如果 去掉预处理 一步会更为简单。而且 从高位到低位 会更加简单。
状态大概设计为 \(f[i][j][lim][zero]\)，表示第 \(i\) 位为 \(j\)、是否卡上界、前面位是否全为 0。转移从高位到低位，枚举下一位是什么即可。
状压 DP——压缩等价状态
标签：状态,复杂度,笔记,网课,搜索,动态,DP,数位 From： https://www.cnblogs.com/David-Mercury/p/18346339