什么是数位dp
-
数位dp是一种计数用的dp，一般是要统计一个区级[l,r]内满足一些条件的数的个数
-
所谓数位dp，就是对数位进行dp，也就是个位、十位等
-
相对于普通的暴力枚举，数位dp快就快在它的记忆化，也就是说后面可能会利用到前面已经计算好的东西，比如我们现在要计算形式为2xxxx的满足某些条件的数字的个数，而这个信息我们可能可以利用计算1xxxx时遗留下来的信息，从而达到一个避免重复计算的效果，因此可以降低时间复杂度
怎么进行枚举
-
最常用的枚举方式是控制上界枚举
-
控制上界枚举就是要让正在枚举的这个数不能超过上界，比如，我们正在枚举上界为321的满足某个条件的数的个数，并且当前我们正在枚举形式1xx，这个时候十位数上的枚举范围很明显是0-9，但如果我们正在枚举形式2xx，这个时候十位数上的枚举范围就只能是0-2了，对于个位数而言，如果我们正在枚举的是21x，也就是前两位都恰好取到了最大的值，则个位的枚举范围只能是0-1，除了这种情况之外，个位数的取值范围都可以是0-9
-
为了表明某个数位上的取值范围，我们常常利用一个bool变量limit来表明该数位前的其他数位是否恰好都处于最大状态，如果不是，则范围为0-9，否则范围将被限制在该数位在上界中的最大值中
-
由于我们只是控制了上界进行枚举，所有对于下界不是零的情况来说，要得到最终结果，我们的操作是solve(r)-solve(l-1)
-
注意，某些问题中，前导零如00xxx的情况也会影响结果，所以要设置一个bool变量lead，当然，在某些问题下，前导零并不影响结果，所有可以不使用它
模板
typedef long long ll;
vector<int> a;
ll dp[20][state]; //不同问题数组的维度可能不同，看具体题目的条件
ll dfs(int pos,int state,bool lead,bool limit) //这里的state可能有多个，看具体题目
{if(pos==n) //n是数组的长度，从高位到地位是0-n-1return 1; //返回值看具体情况if(!limint && !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之类的判断语句ans += dfs(pos+1,state(状态转移),lead&&i==0,limit&&i==a[pos])}if(!limit && !lead)dp[pos][state] = ans;return ans;
}
ll solve(ll x)
{int pos = 0;while(x){a[pos++] = x%10;x /= 10;}reverse(a.begin(),a.end());return dfs(0,state,true,true);
}-
注意，这里的记忆化搜索是有一定的条件的，比如我们在使用之前信息的时候，要保证我们现在是 !limint && !lead 的，因为我们的记忆化搜索要保证通用性，比如1xx的时候我们要使用后两位的信息，为了保证通用性，后两位的信息必须是从00-99的，所有我们在录入信息的时候也要在 !limint && !lead 的前提下
例题一
第一行给出一个数T，表示测试案例的个数，然后下面T行给出一个数n，1-n有多少数包含49，测试数据1 <= T <= 10000,1 <= n <= 263-1
样例
3
1
50
500输出
0
1
15-
思路分析，这里看到要找一个范围内的满足包含49的个数，则我们就要调用我们的数位dp模板进行操作了
#include <bits/stdc++.h>
using namespace std;
const int Max = 99999;
const int Min = 0;
const int inf = 1e6;
const int mod = 1e9+7;
#define M 1000
#define N 1000
#define ll long long
ll dp[20][6];
int digit[20];
ll dfs(int pos,int pre,int sta,bool limit) {if(pos==-1)return 1;if(!limit && dp[pos][sta]!=-1)return dp[pos][sta];int up = limit?digit[pos]:9;ll sum = 0;for(int i=0;i<=up;i++){if(pre==4&&i==9)continue;sum += dfs(pos-1,i,i==4,limit&&i==digit[pos]);}if(!limit)dp[pos][sta] = sum;return sum;
}
ll solve(ll a) {int cnt = 0;while(a>0){digit[cnt++] = a%10;a /= 10;}ll ans = dfs(cnt-1,0,0,true);return ans;
}
int main() {int T;cin >> T;memset(dp,-1,sizeof(dp));while(T--){ll a;scanf("%lld",&a);ll ans = solve(a);cout << a+1-ans << endl; //这里加1是因为ans里面包括了0，所以要减一抵消}return 0;
}例题二
力扣788旋转数字 力扣
https://leetcode.cn/problems/rotated-digits
我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。
如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。
现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？
示例：
输入: 10
输出: 4
解释:
在[1, 10]中有四个好数： 2, 5, 6, 9。
注意 1 和 10 不是好数, 因为他们在旋转之后不变。class Solution {
public:vector<int> v = {1,1,2,0,0,2,2,0,1,2}; //0表示违法数字，1表示可有可无数字，2表示必须要有一个的数字vector<int> nums;vector<vector<int>> dp;int N;int rotatedDigits(int n) {while(n){nums.push_back(n%10);n /= 10;}reverse(nums.begin(),nums.end());N = nums.size();dp = vector<vector<int>>(N,vector<int>(2,-1));return dfs(0,false,true);}
int dfs(int pos,bool sta,bool limit){if(pos==N)return sta?1:0;if(!limit && dp[pos][sta]!=-1)return dp[pos][sta];int up = limit?nums[pos]:9;int sum = 0;for(int i=0;i<=up;i++){if(v[i]==0)continue;sum += dfs(pos+1,sta||v[i]==2,limit&&nums[pos]==i);}if(!limit)dp[pos][sta] = sum;return sum;}
};
