数位DP

#include<bits/stdc++.h>
#define N 22
#define M 11
#define db double
#define ll long long
#define ldb long double
#define ull unsigned long long
using namespace std;
const int h=3,ki=149,mo=998244353;
int mod(int x){return (x%mo+mo)%mo;}
int inc(int x,int k){x+=k;return x<mo?x:x-mo;}
int dec(int x,int k){x-=k;return x>=0?x:x+mo;}
int ksm(int x,int k)
{
	int ans=1;
	while(k){if(k&1)ans=1ll*ans*x%mo;k>>=1;x=1ll*x*x%mo;}
	return mod(ans);
}
int inv(int x){return ksm(x,mo-2);}
int read()
{
	char ch=0;int x=0,flag=1;
	while(!isdigit(ch)){ch=getchar();if(ch==‘-‘)flag=-1;}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();}
	return x*flag;
}
void write(int x)
{
	if(!x)return (void)putchar(48);
	if(x<0)putchar(45),x=-x;
	int len=0,p[20];
	while(x)p[++len]=x%10,x/=10;
	for(int i=len;i>=1;i--)putchar(p[i]+48);
}
int a[N],dp[N][M][2];
int solve(int s)
{
	if(s==0)return 0;
	int n=0;while(s)a[++n]=s%10,s/=10;reverse(a+1,a+n+1);
	
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=a[1];i++)dp[1][i][i==a[1]]=1;
	for(int x=2;x<=n;x++)for(int i=1;i<=9;i++)dp[x][i][0]=1;
	
	for(int x=1;x<n;x++)
	for(int lst=0;lst<=9;lst++)
	if(dp[x][lst][0]||dp[x][lst][1])
	for(int i=0;i<=9;i++)if(abs(i-lst)>=2)
	{
		int f0=dp[x][lst][0];
		int f1=dp[x][lst][1];
		int &g0=dp[x+1][i][0];
		int &g1=dp[x+1][i][1];
		
		if(i<a[x+1])g0+=f0+f1;
		if(i>=a[x+1])g0+=f0;
		if(i==a[x+1])g1+=f1;
	}
	
	int ans=0;
	for(int lst=0;lst<=9;lst++)ans+=dp[n][lst][0]+dp[n][lst][1];
	return ans;
}
int main()
{
	int l=read(),r=read();
	write(solve(r)-solve(l-1));
	return 0;
}

数位DP

原文：https://www.cnblogs.com/Creed-qwq/p/15033049.html