fenxi:

不含前导零且相邻两个数字之差至少为 $\cal{2}$ 的正整数被称为 Windy 数

如何处理不含前导0这个情况？

低于n位数的数要特判，首位数不能是0

题目要求

求从 $\cal{1\, to\, N}$ 中满足Windy数条件的数的个数

状态定义

1. $\cal{last}$：上一个位数的大小（默认<= -2 ， 因为首位数字随便填）
   2.$\cal{f[I][j]}$：(所有最高位是j，并且一共有i位满足windy数条件的集合。属性：数量)

树形分析：

左边分支代表j 是0 ~x − 1，右边分支代表j == x
a. 判断左边的分支：枚举j从0 ~x − 1，res += f[I + 1][j]（abs(j −last)≥2）
b. 进入右边的分支(abs(x − last >= 2))
最终答案就是左边分支之和 + 右边末端的分支(如果走到了右边末端， 表明这个数本身就是满足条件的)

状态方程：

$\cal{F[i][j]+= f[I − 1][k]（abs(k −j)≥2） }$
f数组初始化
$\cal{for(int\,i =0; i <= 9; ++i)f[1][i]= 1;}$

问题：

1. If(abs(x − last >= 2)) last = x Else break;
这段代码，x 和last相差 >= 2, 但是还是能进入右边的分支的？比如j 和last 相差可能小于2？
未作答

2. 处理前导0的代码是什么意思，低于n位数的数要特判是什么意思？
a. 可能会存在这样的情况：
b.$\cal{ A_1 a_2 a_3 a_4 a_5}$ 中 $\cal{a_1}$ 是0， 而题目中规定了不包含前导0，因此，按照题目规定来说是满足条件的，而如果特殊判断的话，这个数是不满足条件的，就会把这个数除掉，因此特殊判断的做法是把1 ~ num.size() − 1 位（即有前导0的数）加上。
c. 例如：当传入的数是357时：
1) 先判断3，res += f[3][1],f[3][2]
2) 再判断5，res += f[2][0], f[2][1],f[2][5]
3) 再判断7，res += f[1][0], f[1][1], f[1][2], f[1][3]
4) 357本身也是，res++
5) 这些计算的都是三位数的数，而1~2位数的数并没有计算，因此要特殊判断
和数字游戏的区别在于：数字游戏的树结构的第一层左分支是从0~x-1 f[num.szie()][0]就是1~n - 1位数，因此不需要再特判，而这道题需要特殊判断前导零的情况。

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 12;
int f[N][N];

//计算f数组
void init()
{
    for(int i = 0; i <= 9; ++i)f[1][i] = 1;
    for(int i = 2; i <= N; ++i)
        for(int j = 0; j <= 9; ++j)
            for(int k = 0; k <= 9; ++k)
                if(abs(k - j) >= 2)
                    f[i][j] += f[i - 1][k];
}
//计算从1 ~ n中满足windy数条件的数的个数
int dp(int n)
{
    if(!n) return 0;
    vector<int> sum;
    while(n)sum.push_back(n % 10), n /= 10;
    int last = -2, res = 0;

    for(int i = sum.size() - 1; i >= 0; i--)
    {
        int x = sum[i];
        //进入左分支
        //由于这里
        for(int j = i == sum.size() - 1; j < x; ++j)
            if(abs(j - last) >= 2)
            //左边的分支当前位是j， f[i + 1][j] 表示最高位是j，一共位数是i的满足windy数的个数
                res += f[i + 1][j];
        //进入右分支的限定条件  
        if(abs(x - last) < 2)break;
        else last = x;
        if(!i) res++;
    }
    //加上1~n位数满足windy条件的数
    for(int i = 1; i < sum.size(); ++i)
    //当是一位数的时候，0也可以加上
        for(int j = 1; j <= 9; ++j)
            res += f[i][j];
    return res;
}

int main()
{
    init();
    int l, r;
    while(cin >> l >> r)
    {
        cout << dp(r) - dp(l - 1) << endl;
    }
    return 0;
}