数位dp

//problem:https://www.luogu.com.cn/problem/P2657
#include <bits/stdc++.h>
#pragma GCC diagnostic error "-std=c++11"
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define PER(I, A, B) for (int I = (A); I >= (B); --I)
#define lson k*2
#define rson k*2+1
#define fi first
#define se second
#define DB(A) cout<<(A)<<endl
#define DB1(A,B,C) cout<<(A)<<" "<<(B)<<" "<<(C)<<"!"<<endl
#define PB push_back
#define Pair pair<int,int>
#define MP make_pair
#define LL long long
#define int LL
using namespace std;
const int maxn=2e5+10;
const int MAX=100;
const int inf=0x3f3f3f3f;   
const int mod=1e9+7;
//head
int n,m;
int dp[MAX][MAX];
int digit[MAX];
//dfs:第k位（从高位到低位），limit==1表示第k+1位是否达到上限（若k为最高位，limit也为0（因为第tot位已达到上限0））， lead==0表示有前导0 
int dfs(int k,bool limit,bool lead,int last) 
{
    if (k==0) return 1;
    if (!limit&&lead&&(dp[k][last]!=-1)) return dp[k][last];
    int upbound=(limit?digit[k]:9);
    int ans=0;
    FOR(i,0,upbound)
    {
        if (abs(i-last)<2) continue;
        if(((lead==0)&&(i==0)))//有前导0 
            ans+=dfs(k-1,limit&&(i==upbound),(!((lead==0)&&(i==0))),444);
        else
            ans+=dfs(k-1,limit&&(i==upbound),(!((lead==0)&&(i==0))),i);
        
        //(!lead)&&(i==0)仅当上一位是前导0且这一位还是0时lead才继续保持0 
        //前导0影响0的统计
    }
    if (!limit&&lead) dp[k][last]=ans;//怎么想出DP转移？ 
    return ans;
}
int solve(int k)
{
    memset(dp,-1,sizeof(dp));
    int tot=0;
    while (k)
    {
        digit[++tot]=k%10;
        k/=10;
    }
    return dfs(tot,1,0,444);    
}
signed main()
{
    while (~scanf("%lld%lld",&n,&m))
    {
        printf("%lld\n",solve(m)-solve(n-1));           
    }
}

数位dp

原文：https://www.cnblogs.com/reshuffle/p/12452530.html