最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

数位DP基础概念 指路：【数位DP基本概念+数位DP记忆化搜索】

题目描述

给定正整数区间 $[l, r]$，求该区间内的 $Windy数$ 个数

Windy数 ：不含 前导零 且 相邻两个数字 之差 至少 为 $2$ 的 正整数

分析

想了解 数位DP 基础概念的，可以看一下最上面我贴的链接，这里不会对 重复内容 进行额外讲解

本题进行搜索时 $st$ 需要记录的 参数 是：前一位数位的数字是多少 （唯一需要思考的地方？）

这样就能保证每次枚举数位上的数字，都能符合题目中的需求了

然后就可以直接 套记忆化搜索的板子 了.....

当然也可以额外开 一个参数 记录当前 是否有前导零，带前导零参数的代码：Windy数-作者:凌乱之风

我这样写的话就不用记录前导零 (基本差不多)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 35;

int l, r;
int a[N], al;
int f[N][N];

int dp(int pos, int st, int op)
{
    if (!pos) return 1;
    if (!op && ~f[pos][st]) return f[pos][st];
    int res = 0, maxx = op ? a[pos] : 9;
    for (int i = 0; i <= maxx; i ++ )
        if (abs(st - i) >= 2)
            res += dp(pos - 1, !i && st == -2 ? -2 : i, op && i == a[pos]);
    return op && st == -2 ? res : f[pos][st] = res;
}
int calc(int x)
{
    memset(f, -1, sizeof f); al = 0;
    for ( ; x; x /= 10) a[ ++ al] = x % 10;
    return dp(al, -2, 1);
}
int main()
{
    cin >> l >> r;
    cout << calc(r) - calc(l - 1) << endl;
    return 0;
}