类型：数位DP
题意：不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。问[A,B]之间windy数的个数。(1 <= A
<= B <= 2000000000 )
思路：
设状态dp[i][d][preAllZero] 表示 d开头的i位数中，当其preAllZero（true 表示前面都是0）的时候，windy数的个数。
为什么有preAllZero这一个状态呢？因为，比如002这个数，如果前面都是0,则是可以的，但如果前面有一位不是0 ，则这两个0违反了windy数的规则，就不行。
转移就不写了。见程序就好。
坑：
没有设preAllZero这个状态，结果一直WA。最近发现老是考虑不完全，结合近两次的原因分析，均为有了思路写程序，写完或者写到一半发现某个地方想错了，然后打补丁，结果没打全，就出了漏洞。总结两点：1：先有清晰的思路，再上阵写程序，只会节省时间。（在纸上思考要时间，你以为敲代码的时候这部分时间就省了？反而是在纸上想完全，然后敲代码的时候就可以不用想了，快啊~~）2：万一敲完发现BUG，打完补丁还不对，最好推倒，重新整理思路，然后再去写（但也不是说要把程序删了重写，或许并没到这个地步，只是没想全而已~）
代码：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int num[100]; long long dp[20][10][2]; long long dfs(int i, int d, bool preAllZero, bool isQuery) { if (!isQuery && ~dp[i][d][preAllZero]) return dp[i][d][preAllZero]; if (i == 1) { return dp[i][d][preAllZero] = 1; } int end = isQuery?num[i-1]:9; long long ans = 0; for (int j = 0; j <= end; j++) { if (!preAllZero && abs(j-d)<=1) continue; ans += dfs(i-1, j, preAllZero && j == 0, isQuery && j==end); } if (!isQuery) dp[i][d][preAllZero] = ans; return ans; } long long cal(int x) { int len = 0; while (x) { num[++len] = x%10; x/=10; } return dfs(len+1, 0, true, true); } int main() { int a, b; memset(dp, -1, sizeof(dp)); while (~scanf("%d%d", &a, &b)) { printf("%lld\n", cal(b) - cal(a-1)); } return 0; }