二刷提高课，题解目录在这里— 提高课的题解目录

此题和上一题类似，但是这里要注意一下是不含前导零的
注意这里补前导零情况的用法
其实应该从后向前容易理解些，因为第一位取0的时候虽然我们前面并没有考虑
但是也是存在windy数的例如013，所以我们后面需要将这些补上
所以这里意为在上一位为零的基础上加上后面的windy数
为什么从1~9而不是0~9？难道0不考虑吗？
不！正是因为我们要考虑为零的情况才会遍历了i
为什么这么说，我们举个例子原本数字为3213，考虑第一位为零的情况
变成0xxx，后面三个可以随便取且均不会再上面循环中出现（上面没考虑前导零）
当我们遍历第一个x从1~9后随后我们开始考虑00xx，这两个依然可以随便取，所以与上一步操作相同
有人可能会有疑问如果从1~9，那0109的情况怎么办呢？
注意这种情况只会在第一个x的1中出现，不会在第二个x中出现

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
const int N=15;
int f[N][N];
int l,r;
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(j-k)>=2)f[i][j]+=f[i-1][k];
            }
        }
    }
}
int dp(int x)
{
    if(!x)return 0;
    vector<int>sum;
    while(x)sum.push_back(x%10),x/=10;
    int res=0,last=-2;
    for(int i=sum.size()-1;i>=0;i--)
    {
        int xx=sum[i];
        for(int j=i==sum.size()-1;j<xx;j++)
        {
            if(abs(j-last)>=2)res+=f[i+1][j];
        }
        if(abs(xx-last)>=2)last=xx;
        else break;
        if(!i)res++;
    }
    for(int i=1;i<sum.size();i++)
    for(int j=1;j<=9;j++)
    res+=f[i][j];


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