$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. f[i][j] 表示共有 i 位且最高位是 j 的 windy 数，last 表示上一个数
2. dp(n) 表示 0 ～ n 中 windy 数的个数
3. 首先预处理，f[i][j] += f[i - 1][k] (abs(j - k) >= 2)
4. 关于前导零，13 符合 windy 数，但 013 却不符合，因为 abs(0 - 1) < 2
5. 处理 nums.size() 位数时，需要注意最高位不能是 0
6. 处理小于 nums.size() 位数时，需要注意最高位不能是 0

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 11;

int f[N][N];

//预处理
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];
}

// 0 ～ n 中 windy 数的个数
int dp(int n)
{
    if(!n) return 0;

    vector<int> nums;
    while(n)
    {
        nums.push_back(n%10);
        n/=10;
    }

    //处理 nums.size() 位数的windy数的个数
    int res=0,last=-2;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        for(int j=i==nums.size()-1;j<x;j++)
            if(abs(j-last)>=2)
                res+=f[i+1][j];

        if(abs(x-last)<2) break;

        last=x;

        if(!i) res++;
    }

    //处理小于 nums.size() 位数的windy数的个数
    for(int i=1;i<nums.size();i++)
        for(int j=1;j<=9;j++)
            res+=f[i][j];

    return res;
}

int main()
{
    init();

    int l,r;

    cin>>l>>r;

    cout<<dp(r)-dp(l-1)<<endl;

    return 0;
}