数位dp
定义
数位dp(Digit Entry DP)是一种计数用的dp，一般就是要哦统计区间[l,r]内满足一些条件的数的个数。所谓数位dp，字面意思就是在数位上进行dp。数位的含义：一个数有个位、十位、百位、千位......数的每一位就是数位啦！
数位dp的思想
数位dp的实质就是换一种暴力枚举的方式，使得新的枚举方式满足dp的性质，然后记忆化就可以了。
模板及例题
模板：
typedef long long ll;
int a[20];
ll dp[20][state]; //不同题目状态不同
ll dfs(int pos,int state,bool lead,bool limit) //变量，状态，前导0，数位上界；注意不是每题都要判断前导零
{
if(pos==0) 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++) //枚举，然后把不同情况的个数加到ans就可以了
{
if() ...
else if()... //一下条件
ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的
//state状态转移要保证i的合法性，比如不能有62，那么当pre==6&&i==2就不合法，这里用state记录pre是否为6即可。
}
if(!limit && !lead) dp[pos][state]=ans;
return ans;
}
ll solve(ll x)
{
int tot=0;
while(x)
{
a[++tot]=x%10;
x/=10;
}
return dfs(tot/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0嘛
}
int main()
{
ll le,ri;
while(~scanf("%lld%lld",&le,&ri))
{
//初始化dp数组为-1,这里还有更加优美的优化,后面讲
printf("%lld
",solve(ri)-solve(le-1));
}
}
例题1：【不要62】（数位dp入门经典题）
描述：给定一个区间，不带4以及没有连续62的数字有多少个；
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[20][2],arr[20];
ll dfs(int pos,int state,bool lead,bool limit)
{
if(pos==0) return 1;
if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
int up = limit?arr[pos]:9;
ll ans = 0;
for(int i=0;i<=up;++i)
{
if(i==4) continue;
if(state && i==2) continue;
ans += dfs(pos-1,i == 6,lead && i==0,limit && i==arr[pos]);
}
if(!limit && !lead) dp[pos][state] = ans;
return ans;
}
ll solve(int x)
{
int tot = 0;
while (x){
arr[++tot]=x%10;
x/=10;
}
return dfs(tot,0,true,true);
}
int main()
{
int l,r;
while(scanf("%d %d",&l, &r) && (l||r))
{
memset(dp,-1,sizeof(dp));
printf("%lld
",solve(r) - solve(l-1));
}
system("pasue");
}