首页 > 代码库 > 浅谈数位DP
浅谈数位DP
在了解数位dp之前，先来看一个问题：
例1.求a~b中不包含49的数的个数. 0 < a、b < 2*10^9
注意到n的数据范围非常大，暴力求解是不可能的，考虑dp,如果直接记录下数字，数组会开不起，该怎么办呢？要用到数位dp.
数位dp一般应用于：
求出在给定区间[A,B]内，符合条件P(i)的数i的个数.
条件P(i)一般与数的大小无关，而与 数的组成 有关.
这样，我们就要考虑一些特殊的记录方法来做这道题.一般来说，要保存给定数的每个位置的数.然后要记录的状态为当前操作数的位数，剩下的就是根据题目的需要来记录.可以发现，数位dp的题做法一般都差不多，只是定义状态的不同罢了.
下面开始针对例题进行分析:
我们要求[a,b]不包含49的数的个数，可以想到利用前缀和来做，具体来说，就是[a,b] = [0,b] - [0,a),(")"是不包括a),我们先求出给定a,b的每个位置的数，保存在数组s中，例如a = 109,那么a[1] = 9,a[2] = 0,a[3] = 1.然后开始dp，我们可以选择记忆化搜索或者是递推，前一种相对于第二种而言简单和较为容易理解一些，所以我们选择记忆化搜索.那么需要记录些什么呢？首先长度是一定要记录的，然后记录当前的数位是否为4，这样就便于在记忆化搜索中得到答案.
然后进行记忆化搜索，记录上一位是否为4和枚举这一位，如果没有限制的话很好办，直接枚举就可以了，但是这样可能会超空间，因此我们每次都必须要判断是否有最大的限制，这里不是很好说，看代码更容易理解：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int a, b, shu[20], dp[20][2]; int dfs(int len, bool if4, bool shangxian) { if (len == 0) return 1; if (!shangxian && dp[len][if4]) //为什么要返回呢？可以画图理解当我们搜到3XXX时，程序运行到1XXX时就已经把3XXX之后的搜索完了，记忆化也是这个用意. return dp[len][if4]; int cnt = 0, maxx = (shangxian ? shu[len] : 9); for (int i = 0; i <= maxx; i++) { if (if4 && i == 9) continue; cnt += dfs(len - 1, i == 4, shangxian && i == maxx); //只有之前有限制现在的达到了上限才能构成限制 } return shangxian ? cnt : dp[len][if4] = cnt; //如果有限制，那么就不能记忆化，否则记忆的是个错误的数. } int solve(int x) { memset(shu, 0, sizeof(shu)); int k = 0; while (x) { shu[++k] = x % 10; //保存a,b的数 x /= 10; } return dfs(k, false, true); } int main() { scanf("%d%d", &a, &b); printf("%d\n", solve(b) - solve(a - 1)); //while (1); return 0; }
再来看一道题：例题2.求a~b中不包含62和4的数的个数. 0 < a、b < 2*10^9
分析：和上一题一样，只需要再判断一下4是否出现和上一位是否为6即可.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int a, b,shu[20],dp[20][2]; int dfs(int len, bool if6, bool shangxian) { if (len == 0) return 1; if (!shangxian && dp[len][if6]) return dp[len][if6]; int cnt = 0, maxx = (shangxian ? shu[len] : 9); for (int i = 0; i <= maxx; i++) { if (i == 4 || if6 && i == 2) continue; cnt += dfs(len - 1, i == 6, shangxian && i == maxx); } return shangxian ? cnt : dp[len][if6] = cnt; } int solve(int x) { memset(shu, 0, sizeof(shu)); int k = 0; while (x) { shu[++k] = x % 10; x /= 10; } return dfs(k, false, true); } int main() { scanf("%d%d", &a, &b); printf("%d\n", solve(b) - solve(a - 1)); return 0; }
例题3:bzoj1026 windy数
对于这道题，我写了一个较为详细的博客：传送门
例题4:找出1~n范围内含有13并且能被13整除的数字的个数.
分析：和例1相比多了一个整除，怎么处理呢？其实只需要在记忆化搜索中增加一个参数mod即可，利用(a * b) % mod = (a % mod) * (b % mod)和（a + b） % mod = （a % mod） + （b % mod）来计算.比如说73 % 10 = ((7 % 10) * 10 + 3) % 10,但要注意本题是要找含有13的数，那么在处理的时候就要进行分类讨论.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n, shu[20], dp[20][20][10]; int dfs(int len, int mod, int zhuangtai, bool shangxian) { if (len == 0) return mod == 0 && zhuangtai == 2; if (!shangxian && dp[len][mod][zhuangtai]) return dp[len][mod][zhuangtai]; int cnt = 0, maxx = (shangxian ? shu[len] : 9); for (int i = 0; i <= maxx; i++) { int tz = zhuangtai; if (zhuangtai != 2 && i != 1) tz = 0; if (zhuangtai == 1 && i == 3) tz = 2; if (i == 1 && zhuangtai != 2) tz = 1; cnt += dfs(len - 1, t, tz, shangxian && i == maxx); } if (!shangxian) dp[len][mod][zhuangtai] = cnt; return cnt; } int main() { while (~scanf("%d", &n)) { memset(shu, 0, sizeof(shu)); memset(dp, 0, sizeof(dp)); int k = 0; while (n) { shu[++k] = n % 10; n /= 10; } printf("%d\n", dfs(k, 0, 0, 1)); } return 0; }
例题5：找出区间内平衡数的个数，所谓的平衡数，就是以这个数字的某一位为支点，另外两边的数字大小乘以力矩之和相等，即为平衡数。
分析：对于这道题，如果一个数中每个数位到支点的距离*这个数位的和为0，那么这个数为平衡数.这样我们定义状态就要考虑力矩和和支点.支点可以在dfs前枚举得到，力矩和可以在处理每个数位的时候得到.但是这个算法是有缺陷的，例如0000,000000也会被统计，我们只需要减去给定范围0全是0的数的个数即可.这里可以进行一个小小的优化，如果力矩和已经为负数，说明已经处理到了支点左边，接着处理下去绝对会小于0,那么回溯即可.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int t; long long dp[19][19][2005]; long long l, r; int shu[20]; long long dfs(int len, int zhidian, int liju, bool shangxian) { if (len == 0) return liju == 0; if (liju < 0) return 0; if (!shangxian && dp[len][zhidian][liju]) return dp[len][zhidian][liju]; long long cnt = 0; int maxx = (shangxian ? shu[len] : 9); for (int i = 0; i <= maxx; i++) { int temp = liju; temp += (len - zhidian) * i; cnt += dfs(len - 1, zhidian, temp, shangxian && i == maxx); } if (!shangxian) dp[len][zhidian][liju] = cnt; return cnt; } long long solve(long long x) { int k = 0; while (x) { shu[++k] = x % 10; x /= 10; } long long ans = 0; for (int i = 1; i <= k; i++) ans += dfs(k, i, 0, 1); return ans - (k - 1); } int main() { scanf("%d", &t); memset(dp, 0, sizeof(dp)); while (t--) { scanf("%lld%lld", &l, &r); printf("%lld\n", solve(r) - solve(l - 1)); } //while (1); return 0; }
经过对以上例题的探讨与研究，自然也就不难得到数位dp模板(...根据实际情况来填)：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int t; long long dp[19][19][2005]; long long l, r; int shu[20]; long long dfs(int len,..., bool shangxian) { if (len == 0) return ...; if (!shangxian && dp[len][...]) return dp[len][...]; //dp数组的内容应和dfs调用参数的内容相同，除了是否达到上限 long long cnt = 0; int maxx = (shangxian ? shu[len] : 9); for (int i = 0; i <= maxx; i++) { ...; cnt += dfs(len - 1,..., shangxian && i == maxx); } if (!shangxian) dp[len][...] = cnt; return cnt; } long long solve(long long x) { int k = 0; while (x) { shu[++k] = x % 10; x /= 10; } return dfs(k,...,1) } int main() { memset(dp, 0, sizeof(dp)); scanf("%lld%lld", &l, &r); //有些题目其实并不需要用到long long printf("%lld\n", solve(r) - solve(l - 1)); //只有满足区间减法才能用 //while (1); return 0; }
总结：
1.如果题目中出现求满足区间[l,r]的符合......性质的数的个数，考虑使用数位dp.
2.思考一下：如果我们只能从前往后一位位枚举当前的数位，要做出这道题，我们需要知道哪些量？利用这些来补充到dfs的调用参数中.
3.套用模板.
浅谈数位DP