数位dp其实就是一种用来求区间[l, r]满足条件的数的个数。数位是指：个十百千万，而在这里的dp其实相当于暴力枚举每一位数。
我们通过把l， r的每位数分解出来，然后分别求r里满足条件的数有多少，l-1里满足条件的数有多少，然后用r的减去(l-1)的就是所求。
数位分解：
int deal(int x) { int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dfs(pos-1, 0, 0, 1); }
我们每一次枚举其实是有上界的，我们要控制我们枚举的这个数不能超过这个上界，此时我们就用limit来限制他。
以HDU-2089为例，他不要4和连续的6和2，此时我们的操作如下：
int dfs(int pos, int pre, int sta, int limit) { if (pos==-1) return 1; if (!limit && dp[pos][sta]!=-1) return dp[pos][sta]; int up=limit?a[pos]:9; int tmp=0; for (int i=0; i<=up; i++) { if (i==4) continue; if (pre==6&&i==2) continue; tmp+=dfs(pos-1, i, i==6, limit&&i==a[pos]); } if (!limit) dp[pos][sta]=tmp; return tmp; }
我们用pos来表示我们当前枚举的这个数的数位(个十百千万...)， pre表示前一位数(有些地方会与上一位数有关)，sta表示是否满足我们所求的条件。
if (pos==-1) return 1;
这里是搜到最底层了，其实也不一定是直接返回-1，也是要满足我们题目所给的条件才行。
if (!limit && dp[pos][sta]!=-1) return dp[pos][sta];
其实这里才是比较难理解的，我们为什么在这里要返回呢？其实就是我们可能在前面已经搜索到了这个值，我们可以不再对他进行下一步的搜索，所以可以直接返回。
int up=limit?a[pos]:9; int tmp=0; for (int i=0; i<=up; i++) { if (i==4) continue; if (pre==6&&i==2) continue; tmp+=dfs(pos-1, i, i==6, limit&&i==a[pos]); }
up表示我这次对这个数位能进行枚举的上届，limit表示上一位是否处于该位的最大值(如233，枚举到十位时，如果上一次枚举的是2，那么我们这次枚举的数最大只能为3，如果上一次枚举的是1，那么对这位就没有影响。limit就我而言它的作用就是限制枚举的数的上界)，在不要62那道题里的限制是不能有连续的62和4，所以枚举的时候特判一下就好了。
代码
/* gyt Live up to every day */ #include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<cstring> #include<queue> #include<set> #include<string> #include<map> #include <time.h> #define PI acos(-1) using namespace std; typedef long long ll; typedef double db; const int maxn = 1e3+10; const int maxm=5000+10; const ll mod = 1e9+7; const int INF = 0x3f3f3f; const db eps = 1e-9; int n, m; int dp[maxn][20]; int a[maxn]; int dfs(int pos, int pre, int sta, int limit) { if (pos==-1) return 1; if (!limit && dp[pos][sta]!=-1) return dp[pos][sta]; int up=limit?a[pos]:9; int tmp=0; for (int i=0; i<=up; i++) { if (i==4) continue; if (pre==6&&i==2) continue; tmp+=dfs(pos-1, i, i==6, limit&&i==a[pos]); } if (!limit) dp[pos][sta]=tmp; return tmp; } int deal(int x) { int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dfs(pos-1, -1, 0, 1); } void solve() { while(scanf("%d%d", &n, &m)!=EOF) { if (!n&&!m) break; memset(dp, -1, sizeof(dp)); printf("%d ", deal(m)-deal(n-1)); } } int main() { int t = 1; //freopen("in.txt", "r", stdin); //scanf("%d", &t); while(t--) solve(); return 0; }