数位DP？数位DFS！

P2657 [SCOI2009] windy 数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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

我们使用DFS解决。数位DFS要设计好状态，考虑好哪些条件会对当前填位造成影响，将其作为参数传递下去。填位，即将该位填上数，并将当前状态DFS下去。回溯的时候各个分支统计好答案，问题解决。

当然，肯定会T。所以我们需要将搜索到的状态记忆化，这样就和DP没有区别了，因为实质上都是避免了重复做事情，该做的一点都没少做。

称之大名鼎鼎的记忆化搜索。

下面，我们通过代码来解释细节：

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int INF=0x7fffffff;

int num[15],len,f[15][15][2][2]; //我们需要放入的参数是len当前位置、last上一位填了谁、flag先前的所有位是否紧贴上界、zero上一位是否是前导零
int dfs(int len,int last,bool flag,bool zero){
	if(!len)return 1; //搜完了，ans++；
	if(~f[len][last][flag][zero])return f[len][last][flag][zero]; //之前搜过，直接返回；
	int res=0;
	rep(i,0,9){ //从0到9每一位试；
		if((i<=num[len]||!flag)&&(abs(i-last)>=2||zero)){
            //如果先前高位已经紧贴上界，则该位不能超过当前位的上界，否则该数会超过上界；其他情况都是合法的
            //windy数的要求是与上一位相差至少2；如果上一位是前导零，则不用管
			res+=dfs(len-1,i,flag&&(i==num[len]),zero&&(!i)); 
            //递归，位置-1，填的数是i，如果先前flag就为1并且该位也紧贴上界，那么flag继续为1，否则为0；如果上一位就是前导零这一位也是0，那么zero继续为0
		}
	}
	f[len][last][flag][zero]=res; //记录并返回
	return res;
}

int solve(int x){
	int tmp=x;
	len=0;
	memset(num,0,sizeof(num));
	while(tmp){
		num[++len]=tmp%10;
		tmp/=10;
	} //先把上界拆了位，放数组里方便查询
	memset(f,-1,sizeof(f)); //dp数组f在处理不同的答案时需要重置
	return dfs(len,11,1,1); //最初的last传递为11，以保证第一位填9时是合法的
}

signed main(){
	std::ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int a,b;
	cin>>a>>b;
	cout<<solve(b)-solve(a-1)<<endl; //[a,b]的windy数，等于[1,b]的减去[1,a-1]的；
    return 0;
}

您会发现，其实状态除了那四个参数以外没有记录别的东西，包括我们现在填上的数（所有位）到底是什么。为什么不用记录呢？

其实，那并不能决定我们下一位可以填什么不可以填什么，属于无用信息。真正有用的，我们已经用这四个参数表示出来了。很巧妙吧？

并且，您要真是把状态表示成那样了，就没有什么可记忆化的了，因为每个状态都是unique的。而只用这四个参数，我们可以搜索到许多完全相同的情况，这时候记忆化就非常有用了。您不妨设想，搜索是一棵树，状态是节点，而len就是深度。在同一个深度上，有很多father不同的节点；而last、flag和zero在这些节点上往往会存在许多相同的，所以状态就在此重复了，我们无需再搜索一次，他们必然和先前搜到的该状态下的答案是一样的。

总结一下数位DFS：

1. 拆位；
2. 设计状态，越简越好，但一定要把必要信息表示全；
3. DFS时，根据参数中的信息，进行条件筛选并填上不同的位搜索下去；
4. 统计答案，记录并返回。
5. 别忘了记忆化。

就OK了。值得注意的是，每一种DP都是灵活多变的，读者需要扩展思维，切莫拘泥于模版。

FIN.