老师以前讲过，这次来复习一下并加深理解。
数位dp听上去是dp，实际上是运用记忆化搜索（虽然二者本质相同）。
该思想用以求出在给定区间内，符合条件的数的个数。条件一般与数的大小无关，而与数的组成有关。
洛谷日报详细讲解
文章讲解的很完美，我就不过多赘述了。
例题：
HDU2089 不要62
模板题，搜索时记录下前一个数用以判断是否有6,2相邻。同时判断当前位置是否为4。
#include<bits/stdc++.h>
using namespace std;
int l,r,cnt;
int dp[20][20],num[20];
int dfs(int pos,int lead,int lim,int la)
{
if(!pos) return 1;
if(!lead&&!lim&&dp[la][pos]) return dp[la][pos];
int l=1,up=lim ? num[pos]:9,sum=0;
for(int i=0;i<=up;i++)
{
if(la==6&&i==2) continue;
if(i==4) continue;
if(lead&&!i) l=0;
sum+=dfs(pos-1,l,lim&&(i==up),i);
}
if(!lead&&!lim) dp[la][pos]=sum;
return sum;
}
int work(int x)
{
memset(dp,0,sizeof(dp));
cnt=0;
while(x)
{
num[++cnt]=x%10;
x/=10;
}
return dfs(cnt,1,1,0);
}
int main()
{
while(scanf("%d%d",&l,&r)&&l&&r)
{
printf("%d\n",work(r)-work(l-1));
}
return 0;
}
Luogu P2657 [SCOI2009]windy数
记录下上一个数，判断与当前数的差是否大于等于2.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,l,r,len;
ll dp[20][20],num[20],ans[20];
ll dfs(ll pos,bool lim,bool lead,ll last)
{
ll sum=0;
if(pos==0) return 1;
if(!lim&&lead&&dp[pos][last]) return dp[pos][last];
int up=9;
if(lim) up=num[pos];
for(int i=0;i<=up;i++)
{
//ans[pos]=i;
if(abs(i-last)<2) continue;
ll l=i;
if(!lead&&l==0) l=-10;
sum+=dfs(pos-1,lim&&(i==up),lead||i,l);
}
if(!lim&&lead) dp[pos][last]=sum;
return sum;
}
ll solve(ll x)
{
memset(dp,0,sizeof(dp));
len=0;
while(x)
{
num[++len]=x%10;
x/=10;
}
return dfs(len,1,0,-10);
}
int main()
{
//freopen("input.txt","r",stdin);
scanf("%lld%lld",&l,&r);
printf("%lld",solve(r)-solve(l-1));
return 0;
}
Luogu P2602 [ZJOI2010]数字计数
分别求每个数的出现次数。但在求0的出现次数时要特判是否有前导0，如果有前导0且当前数也为0，则不计入答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,len;
ll num[20],dp[20][20];
ll dfs(ll pos,ll lim,ll lead,ll dig,ll tot)
{
ll sum=0;
if(pos==0) return tot;
if(!lim&&lead&&dp[pos][tot]) return dp[pos][tot];
ll up=9;
if(lim) up=num[pos];
for(ll i=0;i<=up;i++)
{
sum+=dfs(pos-1,(i==up)&&lim,(i||lead),dig,tot+((i||lead)&&(i==dig)));
}
if(!lim&&lead) dp[pos][tot]=sum;
return sum;
}
ll solve(ll x,ll dig)
{
memset(dp,0,sizeof(dp));
len=0;
while(x)
{
num[++len]=x%10;
x/=10;
}
return dfs(len,1,0,dig,0);
}
int main()
{
//freopen("input.txt","r",stdin);
scanf("%lld%lld",&a,&b);
for(ll i=0;i<=9;i++)
{
printf("%lld ",solve(b,i)-solve(a-1,i));
}
return 0;
}
Luogu P3413 SAC#1 - 萌数
关键点：一个数要成为回文子串，对于它的所有数位至少有一个与该数位的前一位或该数位的前两位（即“前一位的前一位”）相同。
这是因为对称有两种可能：偶数对称（自己编的名字），如“2113”中两个1对称；奇数对称，如“21513”中两个1对称，中间隔了一个5。在搜索时记录下当前位的前两个数以便判断。
注意，在存储一个新的dp状态值时，除了判断前导lead和上限lim外还要判断上上个数是否为-1（即上个数有无前导），若上个数有前导，此时不能赋值，因为有无前导的情况不同。
此外，因为数据过大，所以我用字符读入。通常我们想求solve( r)-solve(l-1)，但此时无法进行l-1操作。实际上我们求得solve( r)-solve(l-1)之后，特判一下l是否符合条件即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1005;
ll len,ans;
ll num[1005],dp[5][maxn][maxn];
char s[1005];
int dfs(int pos,int lead,int lim,int pre,int per,int ok)
{
if(pos>len) return ok;
//if(pos==len&&!ok) return 0;
if(!lim&&!lead&&dp[ok][pre][pos]!=-1) return dp[ok][pre][pos];
int up=lim ? num[pos]:9,sum=0,k;
for(int i=0;i<=up;i++)
{
//k=!i&&lead ? -1:i;
sum=(sum+dfs(pos+1,!i&&lead,lim&&(i==up),i,lead? -1:pre,ok||(i==pre&&!lead)||(i==per&&!lead)))%mod;
}
if(!lead&&!lim&&per!=-1) dp[ok][pre][pos]=(sum+mod)%mod;
return (sum+mod)%mod;
}
int solve()
{
len=strlen(s+1);
memset(dp,0,sizeof(dp));
for(int i=1;i<=len;i++) num[i]=s[i]-'0';
memset(dp,-1,sizeof(dp));
return dfs(1,1,1,-1,-1,0);
}
bool judge()
{
int len=strlen(s+1);
for(int i=1;i<=len;i++)
{
if(s[i]==s[i-1]) return 1;
if(i>=3&&s[i]==s[i-2]) return 1;
}
return 0;
}
int main()
{
//freopen("input.txt","r",stdin);
scanf("%s",s+1);
ans=solve()%mod;
if(judge()) ans--;
scanf("%s",s+1);
ans=(solve()%mod-ans%mod)%mod;
printf("%d",(ans+mod)%mod);
return 0;
}
/*假如此时搜索到了第五位（前导0用-1表示，未搜索到用？表示）
-1 -1 3 4 ? ? ? ? ?
1 2 3 4 ? ? ? ? ? 二者此时ok,pre,pos值相同，但下面一行的数*/
P4127 [AHOI2009]同类分布
记录前面数字的和dig与所有数字组成的数sum。
sum的值太大，这里我们运用取模运算来减小其数值。而正好我们要求dig被sum整除，以dig为模数，判断sum取模后答案是否为0岂不美哉？因为dig值不确定而其范围又较小，于是我们枚举mod累积答案。当搜索到最后一个数再判断mod是否等于dig并判断取模后的sum是否为0即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l,r,ans;
ll dp[20][200][200];
int cnt,num[20],mod;
ll dfs(ll pos,ll lead,ll lim,ll dig,ll sum)
{
if(pos==0&&dig==0) return 0;
if(pos==0) return dig==mod&&sum==0;
if(!lead&&!lim&&dp[pos][dig][sum]!=-1) return dp[pos][dig][sum];
int up=lim? num[pos]:9;
ll res=0;
for(int i=0;i<=up;i++)
{
res+=dfs(pos-1,lead&&!i,lim&&i==up,dig+i,((sum*10)+i)%mod);
}
if(!lead&&!lim) dp[pos][dig][sum]=res;
return res;
}
ll solve(ll x)
{
cnt=ans=0;
while(x)
{
num[++cnt]=x%10;
x/=10;
}
for(mod=1;mod<=9*cnt;mod++)
{
memset(dp,-1,sizeof(dp));
ans+=dfs(cnt,1,1,0,0);
}
return ans;
}
int main()
{
//freopen("input.txt","r",stdin);
scanf("%lld%lld",&l,&r);
printf("%lld",solve(r)-solve(l-1));
return 0;
}