数位 \(DP\)
前言
终于有时间来填这个大坑了啊。
数位 \(DP\) 是一种比较冷门的动态规划问题。
其一般都具有以下特征：
出现连续的数字
失去某一位，不能选哪个数
整除某个数字
在一个区间里面寻找合法解的数量
打法
递推法 和 递归法在数位 \(DP\) 中较为常见。
递推法为先处理出普遍的情况，再一位一位填数。
而递归法是运用记忆化搜索的思想，转 \(DP\) 为搜索，在枚举的过程中即填完数。常数较大，但好写好理解。
这里着重讲一下 递归法 的模板。
我们的传参中有这么几个：
\(pos\) : 目前在哪一位
\(val\) : 此位选的值
\(limit\) : 关于这一位是否有最大选的限制 (会细讲)
\(head\) : 此位是否为前导零
最后是记忆化搜索最需要的东西 : \(dp\) 数组。
其实这个东西是有板子的，就像数据结构一样。
\(limit\) 用法详解
由于我们是在一位一位的枚举，一位一定是有取的最大数字的。
正常来说，一个个位数字的取值范围是在 \([0 , 9]\)
但是我们举个例子：
\[114514 \]假设我们第一位和第二位均取 \(1\) , 而第三位我们显然不能取 \([0 , 9]\) , 而是 \([0 , 4]\)
但如果是在第二位我们取 \(0\) , 显然我们此时可以取 \([0 , 9]\) 了。
于是我们得到了 \(limit\) 的转移式：
\[limit' = limit \ \& \ (i == Up) \]\(i\) 为我们这次的枚举量， \(Up\) 为在取满时的最大值(和 \([0 , 4]\) 一样)
还是很好想的对吧
标签：val,int,pos,limit,DP,dp,数位 From： https://www.cnblogs.com/hangry/p/18290704