数位DP，一般的套路是

$f_{i,j}$表示长度为$i$，最高位为$j$的...数的个数

一般会考区间计数，这时候需要一个函数来利用$f$的值计算区间$(0,a)$或$(0,a]$的解，

然后只要调用$calc(b)-calc(a-1)$或$calc(b+1)-calc(a)$即可，其中，$calc$为上文提到的计算函数。

例题为BZOJ 1026 windy数。

本题，按照传统数位DP，设$f_{i,j}$表示长度为$i$，最高位为$j$的windy数的个数。

那么首先枚举$i$，$j$；然后枚举第$i-1$位数时的最高位$k$即可。这里预处理的DP是$O(n^3)$的。

那么后面来推$calc$函数。

先计算长度小于参数$c$的个数，然后计算最高位小于$A[m]$的数吗，然后一位一位下推，如果两个数的差值比1小，那么说明下面就不能这样做了，因为不是windy数了。

那我们来看代码

# include <stdio.h>
# include <string.h>
# include <stdlib.h>

using namespace std;

int f[12][10];
// f[i,j] 表示 长度为i，最高位为j的windy数个数。 

// 计算(0,a)范围内的windy数个数 
int js(int a) {
	int m=0,A[20];
	int tmp=a;
	while(tmp) {
		A[m++]=tmp%10;
		tmp/=10;
	}
	int ret=0;
	for(int i=1;i<m;++i) 
		for (int j=1;j<10;++j)
			ret+=f[i][j];
	for (int i=1;i<A[m-1];++i) ret+=f[m][i];
	for (int i=m-1;i>=1;--i) {
		for (int j=0;j<A[i-1];++j) 
			if(abs(j-A[i])>1) ret+=f[i][j];
		if(abs(A[i]-A[i-1])<=1) break;
	}
	return ret;
}
int main() {
	memset(f,0,sizeof(f));
	for (int i=0;i<10;++i) f[1][i]=1;
	for (int i=2;i<=11;++i)
		for (int j=0;j<10;++j)
			for (int k=0;k<10;++k) 
				if(abs(j-k)>1) f[i][j]+=f[i-1][k];
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d\n",js(b+1)-js(a));
	return 0;
}