数位dp一般针对统计某个区间符合一个或多个条件的数的数量，因为算法名字叫数位dp，所以我们需要对数位进行枚举
思路
考虑，传统做法，例如统计[L, R]之间有多少个数，该数至少含有一个1，传统做法，直接暴力，算出[0, R], [0, L - 1], 类似于前缀和一样，然后相减即可。但是复杂度无疑来到了o(N²), 还带有一个很大的常数。R一旦到1e6左右就寄了。
而数位dp提供了一种新思路，利用记忆化搜索（dp的一种实现方式），枚举数位的方式，减少了很多复杂状态的重复计算。
举个例子：
例如现在是算[0, 114519]
已经枚举完了11，现在是11XXXX，这个时候第一个X等于1，2，3的时候，种类数相同，因为后面的3个X可以任意枚举0-9（等于4的时候就不行，后面的第二个x就有5的上限的限制），这就是重复状态，数位dp，可以将这重复状态的计算给去掉。
还有一个特殊的限制是前导0签到爆0，例如4231，我们在记忆化dfs的时候，会出现00XX的情况，因为需要枚举0，0可能在中间（属于合法状态），但是如果前面全是0的这种情况（有些题目是合法的，有些题目不合法，根据题目而来）。所以我们需要维护以下几种东西：
1、pos 当前位置pos
2、limit 当前数位pos是否到达枚举上限
3、lead 前导0是否存在
4、others 其他题目给出的限制条件
模板
该算法模板大部分基本一致，dfs功底扎实的一下就能看懂！
int f[pos][limit][lead]
int dfs(int pos, ..., bool limit, bool lead)
{
if (pos == cnt)//枚举到最后一位
return 1;//不一定是1 有时候是题目限制
int ans = 0;
if (f != -1) return f;//该状态已经计算过了
for (int v = 0; v <= (limit ? A[pos] : 9); v++)//根据limit判断枚举上限
{
//limit 和 lead 与当前位置的限制关系都是 &&
ans += dfs(pos + 1, limit && v == A[pos], lead && v == 0);
}
return f = ans;
}
int fx(int x)
{
if (x == 0)return 0;
cnt = 0;
memset(A, 0, sizeof(A));
memset(dp, -1, sizeof(dp)); //初始化为-1 判断是否存在该状态 某些状态0也算 所以不能赋值为0
while(x) A[cnt++] = x % 10, x /= 10;
reverse(A, A + cnt);//反转一下 还正着从左往右数 理解前导0
return dfs(0, true, true);//第一位有限制 true 前缀都看为0 为true
}
例题
不要62
传送门
Des
数位不能存在62连起来，也不能含有4。
Solution
注意：这里它是个车牌号，前导0是合法的，所以我们不用判断前导0，多维护一个信息，上一位是几，如果last = 6， pos = 2，就跳过不用枚举，pos = 4的情况也跳过就行。
Code
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int cnt, A[10];
int f[12][20][2];//pos last limit
int dfs(int pos, int last, int limit)
{
if(pos == cnt) return 1;
if(f[pos][last][limit] != -1) return f[pos][last][limit];
int ans = 0;
for(int v = 0; v <= (limit ? A[pos] : 9); ++v)
{
if((last == 6 && v == 2) || v == 4) continue;
ans += dfs(pos + 1, v, limit && A[pos] == v);
}
return f[pos][last][limit] = ans;
}
int fx(int x)
{
cnt = 0;
memset(A, 0, sizeof A);
memset(f, -1, sizeof f);
while(x) A[cnt++] = x % 10, x /= 10;
reverse(A, A + cnt);
return dfs(0, 11, true);//11表示上一位不存在
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0);
int L, R;
while(cin >> L >> R, L || R)
{
cout << fx(R) - fx(L - 1) << "\n";
}
return 0;
}
数位小孩
传送门
Des
限制：
相邻数位和是否是素数，
至少含有一个1，
没有前导0，
Soluiton
素数和好说，类似于上一题，记录一个last（上一位），判断last + pos是否为素数就行，
至少含有一个1，这个我们不能因为当前pos不是1，而直接return，因为后面的位可能可以枚举1，所有用flag变量，记录当前的数位是否有1，直到最后枚举完所有数位，返回flag（这也是为什么，return 那里不一定是1，也有可能是限制条件）
Code
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define int long long//记得LL
using namespace std;
int cnt, A[20];
int f[20][20][2][2][2];
int vis[40];
int dfs(int pos, int last, bool limit, bool lead, bool flag)
{
if(pos == cnt) return flag;
if(f[pos][last][limit][lead][flag] != -1) return f[pos][last][limit][lead][flag];
int ans = 0;
for(int v = 0; v <= (limit ? A[pos] : 9); ++v)
{
if(lead)
ans += dfs(pos + 1, v, limit && v == A[pos], lead && v == 0, flag || v == 1);
else if(vis[v + last])
ans += dfs(pos + 1, v, limit && v == A[pos], lead && v == 0, flag || v == 1);
}
return f[pos][last][limit][lead][flag] = ans;
}
int fx(int x)
{
cnt = 0;
memset(A, 0, sizeof A);
memset(f, -1, sizeof f);
while(x) A[cnt++] = x % 10, x /= 10;
reverse(A, A + cnt);
return dfs(0, 11, true, true, false);
}
signed main()
{
vis[2] = 1;
vis[3] = 1;
vis[5] = 1;
vis[7] = 1;
vis[11] = 1;
vis[13] = 1;
vis[17] = 1;
int L, R;
cin >> L >> R;
cout << fx(R) - fx(L - 1) << "\n";
return 0;
}
数字计数
传送门
Des
出现0 - 9 的每个数位的次数
Solution
一下子统计出来，不太好搞，一次找一个数位即可。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define int long long
using namespace std;
int cnt, A[20];
int dight;
int f[20][20][2][2];//pos cntd lead limit
int dfs(int pos, int cntd, bool lead, bool limit)
{
if(pos == cnt) return cntd;
if(f[pos][cntd][lead][limit] != -1) return f[pos][cntd][lead][limit];
int ans = 0;
for(int v = 0; v <= (limit ? A[pos] : 9); ++v)
{
//不能合起来，计算0的时候 v == dight 0会多算
if(lead && v == 0)
ans += dfs(pos + 1, cntd, true, limit && v == A[pos]);
else
ans += dfs(pos + 1, cntd + (v == dight), false, limit && v == A[pos]);
}
return f[pos][cntd][lead][limit] = ans;
}
int fx(int x)
{
cnt = 0;
memset(A, 0, sizeof A);
memset(f, -1, sizeof f);
while(x) A[cnt++] = x % 10, x /= 10;
reverse(A, A + cnt);
return dfs(0, 0, true, true);
}
signed main()
{
int L, R;
cin >> L >> R;
for(int i = 0; i <= 9; ++i)
{
dight = i;
cout << fx(R) - fx(L - 1) << " ";
}
return 0;
}
完结撒花。
参考一下两边博客，写了一些自己理解的其他东西。
[博客1]（https://zhuanlan.zhihu.com/p/348851463）
[博客2]（https://zhuanlan.zhihu.com/p/465885658）