数位dp是一种计数用的dp，一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp，字面意思就是在数位上进行dp咯。

数位还算是比较好听的名字，数位的含义：一个数有个位、十位、百位、千位......数的每一位就是数位啦！

之所以要引入数位的概念完全就是为了dp。数位dp的实质就是换一种暴力枚举的方式，使得新的枚举方式满足dp的性质，然后记忆化就可以了。

windy 数 [P2657]

题目描述

不含前导零且相邻两个数字之差至少为 22 的正整数被称为 windy 数。windy 想知道，在 aa 和 bb 之间，包括 aa 和 bb ，总共有多少个 windy 数？

#include<bits/stdc++.h>
#define R register int
using namespace std;
int a,b,l,num[12],dp[12][10];
//dp[i][j]表示第i位前一个数为j的合法方案数 
inline int dfs(int len,int up,int ok)
{
    R i,ed,ans=0; //递归边界，既然是按位枚举，最低位是 1
    if(len<1) return 1; //合法即返回 1 
    if(!ok&&~dp[len][up]&&up!=-3) return dp[len][up];
    //没有最高位限制，已经搜过了
    //常规写法都是在没有限制的条件记忆化，这里与下面记录状态是对应
    ed=ok?num[len]:9; //根据ok判断枚举的上界up
    for(i=0;i<=ed;i++) //计算 
	    if(abs(i-up)>=2)
        ans+=dfs(len-1,(!i&&up==-3)?up:i,ok&&(i==ed));
    //状态转移 根据有无前导 0搜索 
    if(!ok&&up!=-3)  dp[len][up]=ans;
	//没有最高位限制且没有前导0时记录结果 
    //对应上面的记忆化 
    return ans;
}

inline int sovle(int x)//数位分解 
{
    l=0;
    while(x) num[++l]=x%10,x/=10;
    return dfs(l,-3,1);
}

int main()
{
    scanf("%d%d",&a,&b);
    memset(dp,-1,sizeof(dp));
    printf("%d",sovle(b)-sovle(a-1));
}

 

烦人的数学作业 [P4999]

#include<bits/stdc++.h>
using namespace std;
const int N=205;
typedef long long LL;
const LL mod=1e9+7;
LL a[N],dp[N][N],n,m,t;

LL dfs(LL x,int y,int st)
{
	if(x<1) return y;
	if(!st&&~dp[x][y]) return dp[x][y];
	int re=st?a[x]:9;
	LL sum=0;
	for(int i=0;i<=re;i++)
	{
		sum=(sum+dfs(x-1,y+i,(st&&re==i)))%mod;
	} 
	if(!st) dp[x][y]=sum;
	return sum;
}

LL solve(LL x)
{
	t=0;
	while(x)
	{
		a[++t]=x%10;
		x/=10;
	}
	return dfs(t,0,1)%mod;
}

int main()
{
	int t;
	cin>>t;
	memset(dp,-1,sizeof dp);
	while(t--)
	{
	    cin>>m>>n;
	    cout<<(solve(n)-solve(m-1)+mod)%mod<<endl;
	}
	return 0;
 }