今天，我向大家介绍一种特殊的DP类型——数位DP。
数位DP这类题目一般不会出现在提高组及以下的比赛中（今后出现了当我没说【滑稽】），更可能出现在省选及更高级别的比赛上，但是还是挺好理解的一种动态规划类型。
题目模型
这种动规问题特殊在哪里呢？数位DP，顾名思义，这是一种用于处理“数字”的DP类型。换句话说，数位DP的问题模型可以简化为给出一个下限a，一个上限b，求[a,b]中满足题意的数有几个。
解决方法
既然是“数字”的问题，那解决方法必然也和”数字“有关。
1、我们可以对数字的每一位进行动规，枚举满足条件的数字每一位可以是多少。
2、判断当前数字是否超过上限的对应数字。如果没有的话，那么接下来的数字可以任意取；如果等于上限的对应数字，那么接下来的数字最大只能等于对应的数字。这样，上限的问题就解决了。
3、可以采用前缀和的思想，用[0,b]的答案减去[0,a-1]的答案，这样下限的问题也解决了。 举个栗子通过文字来介绍数位DP，非常抽象。按照惯例，我们还是通过几道例题来深入了解一下数位DP（题目来源洛谷，侵删）。
洛谷P2657
Problem
这道题是经典的数位DP类型的题目。
阅读题目发现，我们要求在区间[A, B]上，满足无前导零且相邻数字相差大于等于2的数字个数。这符合我们对数位DP的认知。我们计算[0, B]的答案，减去[0, A - 1]的答案，这样就把下限处理好了。 接下来，我们思考如何计算[0, B]之间的windy数。 首先，我们要先把B拆开存在数组里，方便后续对B的每一个数字的使用。
for (len = 0; x; x /= 10) a[++len] = x % 10;
如果不考虑上限，我们显然可以很快求出以i开头，长度为j的数字中，windy数的数量，转移方程如下：
转移方程
显然，位数小于B的windy数可以通过f数组来求出来
for (int i = 1; i < len; ++i)
for (int j = 1; j <= 9; ++j)
sum += s[i][j];
位数等于B，但是第一个数字小于B的windy数也可以通过f来快速求出。
for (int i = 1; i < a[len]; ++i) sum += s[len][i];
接下来就是数位DP中最容易绕晕的部分了，因为我们要开始考虑上界对问题的影响了。
由于最高位小于上界的已经处理过了，所以现在我们要处理的数最高位一定和上界相同。那么是不是转化成一个子问题了呢？
for (int i = len - 1; i >= 1; --i) {
for (int j = 0; j < a[i]; ++j) {
if (abs(j - a[i + 1]) >= 2)
sum += s[i][j];
}
if (abs(a[i] - a[i + 1]) < 2) break;
if (i == 1) sum++;
}
数位DP的题目大多比较相似，我就不再多举例了。
需要注意的是，处理这类题目的时候，要想清楚什么时候会碰到上限，什么时候可以不考虑上限快速求解，同时还要注意边界情况。
最后的最后，动规题目的精髓在于多看，多练。
【信息学竞赛从入门到巅峰】，一个专注于分享OI/ACM常用算法及知识的公众号。
网友评论