[笔记]数位dp例题及详解-下

【接上回】- 数位 dp 例题及详解 - 上

共 \(4\) 道难度较高、较有思考性的题。

附上数位 dp 题单：https://www.luogu.com.cn/training/494976#problems

小小的总述：

数位 dp 是这样的，状态表示越简洁，dp 数组越小巧，进而时空消耗就越少。所以我们刷题的时候，可以先无脑把 \(f\) 数组的每一维都设为与当前状态相关的所有变量，然后在此基础上，再用下面的方法进行优化：

逐步思考哪些状态是一样的，进而优化维度或者每一维的大小。（最重要，是数位 dp 的精髓，可以同时优化时间和空间）

例：几乎所有数位 dp 题

搜索中途可能有一些状态需要剪枝。（只能优化时间，记忆化越强效果越不明显，所以其实也不是那么重要，但是应该作为写搜索的一个习惯）

例：Round Numbers S、Segment Sum

思考 dp 数组有没有冗余空间（根本搜索不到的那种）。（只能优化空间，可应对一些卡常的题）

例：Balanced Numbers

\(\textbf{INDEX}\)

SP10606 Balanced Numbers ~ 题解

CF1073E Segment Sum ~ 题解

CF55D Beautiful numbers ~ 题解

P3413 萌数 ~ 题解