数位dp详解

数位dp详解

一类问题的描述是：给你一个数字区间，问你区间中满足条件的数的个数。

比如：求区间【1， 1000】中数字1不重复出现的数字的个数，像11， 110， 111这类数字都是不满足条件的。

一般思路就是把区间所有的数字都枚举一遍，逐个判断是否满足题意，但这类题目往往具有庞大的数据规模，比如有的题目所给的区间是【1， 10 ^20】，暴力枚举肯定超时，这就要求我们寻找一种更高效的算法，这便有了数位DP。

数位DP，就是把一个数字划分成个位、十位、百位……在数位上寻找状态转移方程，在讲解数位DP前我们先来看看为什么要用到数位DP：

随便拿个数字54321举例，划分数位后，每一位都有0~9十种情况，暴力枚举的话共有10^5种情况，乍一看比传统的暴力枚举12345个数复杂度更高，但划分数位后我们可以对这10^5种情况做极大的优化。

首先每一位都是有限制的，当万位是4时千位固然可以枚举0~9，但当万位是5时千位只能枚举0~4，这就减少了一些情况，但优化效果不是很显著；

然后再来看核心的优化，我们用位数来划分子问题，那么5位数的状态可以由4位数的状态在条件满足时转移得到，比如说3XXXX可以由0XXX、1XXX、2XXX……9XXX转移得到（对0的情况有疑问的先忽略一下，在下面会有专门的讲解），同样4XXXX也可以由0XXX、1XXX、2XXX……9XXX转移得到，这就出现了子问题重叠，如果将4位数的状态记录一下的话将是极大的优化。

数位DP的大体思想说完了，现在看一下具体实现，先给出伪代码（因为DP部分千变万化，没法给出具体的模板）：

#include using namespace std;typedef long long llconst int maxn = 20;//一般题目给出的数字不会超过20位int a[maxn];//记录每一位的上限，这里顺序上注意一下，如果题目给的区间是【1,54321】的话a中记录的是1，2，3，4，5，即高位在后int dp[maxn][STATE];//dp[i][j]表示第i位状态为j时满足题目要求的数字的数量，这里数字的位数是从第0位开始的，STATE要根据题目来定

//if(!limit)的含义在下面会讲ll rec(int pos, int state, bool limit) { if (pos == -1) return 1;//最低位是第0位，-1就说明枚举结束，返回绘值不一定是1，根据题目来定 if (!limit && dp[pos][state] != -1) return dp[pos][state];//记忆化搜索,注意dp一开始都标记为-1 int up = limit ? a[pos] : 9;//每一位都是有限制的，参考上面讲的54321的例子 ll ans = 0;//开始dp计数 for (int i = 0; i <= up; i++) { //这里根据题目写状态转移方程 ans += rec(pos - 1, state/*状态转移*/, limit && i == a[pos]);//一般情况下这么写 } if (!limit) dp[pos][state] = ans;//计数完毕，记录状态 return ans;}ll solve(ll x) { int pos = 0; while (x) {//划分数位 a[pos++] = x % 10; x /= 10; } return rec(pos - 1, state/*根据题目而定*/, true);//注意limit开始要为true，不然整个过程就都没有限制了}int main(){ ll L, R; while (scanf("%d %d", &L, &R) == 2) { memset(dp, -1, sizeof(dp)); printf("%lld\n", solve(R) - solve(L - 1)); } return 0;}

关于if(!limit), 举例：

题目要求：求【1， 210】上1不能连续出现(11、110、111都是不合法的)的数字的个数

状态:dp[pos][pre]:当前枚举到pos位，前面一位枚举的是pre(更加前面的位已经合法了)的满足题意的数字的个数。

如果不判limit就直接记忆化, 那么假设我们第一次枚举了百位是0，显然后面的枚举limit=false，也就是数位上0到9的枚举，然后当我十位枚举了1，此时考虑dp[0][1],就是枚举到个位，前一位是1的个数，显然dp[0][1]=9;(个位只有是1的时候是不满足的)，这个状态记录下来，继续dfs，一直到百位枚举了2，十位枚举了1，显然此时递归到了pos=0,pre=1的层，而dp[0][1]的状态已经有了即dp[pos][pre]!=-1；此时程序直接return dp[0][1]了，然而显然是错的，因为此时是有limit的个位只能枚举0，根本没有9个数，这就是状态冲突了。

关于前导0，首先0自然是要枚举的，拿54321来说，如果万位是0，那么此时数字就成了4位数，显然【1,54321】中4位数的情况也要算上，所以枚举0是没有错误的，但枚举0对于有的题目会有影响，对于某些状态转移方程忽略了前导0就会出错，这里给出考虑前导0的伪代码：

#include using namespace std;typedef long long llconst int maxn = 20;int a[maxn];int dp[maxn][STATE];ll rec(int pos, int state, bool limit, bool lead) { if (pos == -1) return 1; if (!limit && !lead && dp[pos][state] != -1) return dp[pos][state]; int up = limit ? a[pos] : 9; ll ans = 0; for (int i = 0; i <= up; i++) { if (lead) { } else { } //...... ans += rec(pos - 1, state/*状态转移*/, limit && i == a[pos], lead && i == 0); } if (!limit && !lead) dp[pos][state] = ans; return ans;}ll solve(ll x) { int pos = 0; while (x) { a[pos++] = x % 10; x /= 10; } return rec(pos - 1, state/*根据题目而定*/, true, true);}int main(){ ll L, R; while (scanf("%d %d", &L, &R) == 2) { memset(dp, -1, sizeof(dp)); printf("%lld\n", solve(R) - solve(L - 1)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。