未完，明天更新

在开始之前，我们先来看一道题——题目链接

题目要求，相邻两位的差大于等于2，那么我们先来构造一个试一试。

比如说\(15246\)这个数，我们先取第一位为\(1\)，然后第二位是\(5\)，\(5-1=4>2\)所以符合条件，第三位是\(2\)，\(5-2=3>2\)符合条件，第四位是\(4\)，\(4-2=2\)符合条件，第五位是\(6\)，\(6-4=4\)符合条件，所以这个数使符合条件的。

那么问题来了，如果我们一个数一个数的构造，复杂度显然是有问题的，我们就需要对其进行优化。来看\(15246\)和\(96246\)这两个数，他们都是符合规则的，而且它们后三位是相同的，那么我们很容易可以联想到，只要倒数第四位与\(2\)的差符合规则，那么只要后三位是\(246\)就一定是符合规则的，也就是说我们根本不需要去重复判断。

有没有想到什么熟悉的东西？没错，记忆化！从前往后构造，当后几位已经被处理过，我们就可以直接使用，而不是重新判断，大大节省了时间。

那么判断也就很简单了，只需要枚举下一位，看和当前位的差是否满足规则即可。题目又要求不含前导零，也就是除了\(0\)本身以外的任何数不准用\(0\)开头，那么从第一位开始，我们记录有前导\(0\)当有一位不为\(0\)之后，把状态记录为不含前导零，前导零后的第一个不为零位无任何限制。

那么我们来看一下程序吧

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<cmath>
#define ll long long
#define gc() getchar()
#define maxn 15
using namespace std;

inline ll read(){
    ll a=0;int f=0;char p=gc();
    while(!isdigit(p)){f|=p=='-';p=gc();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
    return f?-a:a;
}
void write(ll a){
    if(a>9)write(a/10);
    putchar(a%10+'0');
}

int x,y,d[maxn],l;
ll f[maxn][maxn];
ll dfs(int pos,int pre,bool limit,bool lead){  //pos表示从后往前数第pos位，pre记录前一位我们选择的数值，limit记录当前是不是卡着最大值，如果卡着最大值就不能从[0,9]中任意选数，而是在[0,区间右端点当前位的数值]之间选数，lead就是记录前导零的问题了
    if(!pos)return 1;  //如果所有位都已经构造完了，说明这是一个合法数值，贡献加一
    if(!limit&&!lead&&~f[pos][pre])return f[pos][pre];  //如果已经处理过特殊要求均相同的情况，直接返回答案，避免重复计算
    int up=limit?d[pos]:9;ll ans=0;  //up就是当前位选数的右端点
    for(int i=0;i<=up;++i){  //枚举构造
        if(abs(i-pre)<2&&!lead)continue;  //如果不合法则跳过
        ans+=dfs(pos-1,i,limit&&i==d[pos],lead&&!i);
    }
    if(!limit&&!lead)f[pos][pre]=ans;  //这里有多种写法，其实就是要求你把各种特殊状态都记录下来
    return ans;
}

ll solve(int k){
    l=0;
    while(k){  //这里是为了记录一下当前范围最大是几位
        d[++l]=k%10;
        k/=10;
    }
    return dfs(l,0,1,1);
}

int main(){memset(f,-1,sizeof f);
    x=read();y=read();
    write(solve(y)-solve(x-1));  //答案要求是[x,y]之间的windy数，所以减去[0,x)的windy数即可
    return 0;
}

数位DP入门详解+题目推荐

原文：https://www.cnblogs.com/hanruyun/p/11454535.html