动态规划的理解#

动态规划的核心不是数组或循环，而是两个性质：

DP要解决的问题就是把重复计算过的状态存下来。在数学本质上，它把一个问题拆成若干有依赖关系的子问题，并避免重复计算。

记忆化搜索#

实际上，记忆化搜索是DP的一种实现方式，可以理解成DFS+缓存表。

它的思考方式是：我先不管状态的计算顺序，需要哪个状态，我就递归去算哪个状态，算过之后记下来，下次直接返回。

记忆化搜索更像：我要 f(n)，所以我去找 f(n-1), f(n-2)。从问题目标出发，考虑要得到当前状态的答案，需要哪些子状态。

递推 DP 更像：我已经知道 f(0), f(1)，所以我推出 f(2), f(3)。从状态转移顺序出发，考虑当前状态可以更新哪些后续状态。

当状态转移类似DFS时，例如树形DP，图上DP；或者状态顺序不好确定时，考虑使用记忆化搜索。

常用于子序列计数、数位DP、整除性统计

若当前数字为 $x$ ，且 $x \bmod m=r$ ，在十进制数 $x$ 的末尾追加数字 $d$ 后，新数字为： $x' = 10 \cdot x + d$ 。

因此新余数为 $r' = (10 \cdot r + d) \bmod m$ ，更一般地，在 $B$ 进制下有 $r' = (B \cdot r + d) \bmod m$ 。

一般使用这个方法时，对后续转移而言，相同余数的数字是等价的。