首先我们主要采用的方法是记忆化搜索

可以解决的问题:对于一些求区间中满足某种特性的题目我们直接使用数位dp记忆化搜索便可以解决,区间递归中需要保存的信息
通过数位之间的关联可以直接练习到一起
1.优势
    (1)记忆化对于已经搜索过的状态可以直接使用，极大的降低了时间复杂度
    (2)相比较与迭代的写法简单好写


2.基本模板如下
// 代码来源题目不要62的数位dp记忆化
#include <bits/stdc++.h>
using namespace std;
const int N=30;
int f[N][N];
int num[N];

// 这个状态是否可以被固定 如果那么维度的数量就够了

int dfs(int pos,int limit,int st){
    // 判断不合理状态比如st位负数
    int &v=f[pos][st];// 在这之前是否有一些不合理的状态
    if(!pos) return 1;
    if(~v&&!limit) return v;
    int upper= limit ? num[pos] : 9;
    int res=0;
    for(int i=0;i<=upper;i++){
        if(i==4) continue;
        if(st==6&&i==2) continue;
        res+=dfs(pos-1,limit & i==upper,i);
    }
    return limit ? res : v=res;
}

int dp(int x){ // 是否需要考虑直接枚举某一个参数
    int pos=0;
    while(x) num[++pos]=x%10,x/=10;
    return dfs(pos,1,0);
}

int main(){
    memset(f,-1,sizeof f);
    int l,r; 
    while(cin>>l>>r,l||r) 
        cout<<dp(r)-dp(l-1)<<endl;
}


模板补充一种方式

我们可以发现有些时候我们使用dp的话每一个位置数的总的方案数并不是很多(常见于mod或者某一维度很小的取余操作中)

如果需要路径记录我们可以开一个结构体来记录整个路径

[牛客的Kevin的哈希构造](https://ac.nowcoder.com/acm/contest/57683/F)

依照题目意思总的方案位 55*55*1000 是不超过 1e7 所以是可以进行记忆化搜索 

int t,n,m,b,p,k;
string s;

bool f[M][M][N];
struct code{
    int ne,cnt,hash,u;
}dp[M][N][N];// 使用结构体加入路径记录

void dfs(int pos,int cnt,int hash){
     if(pos>=n || cnt>k) return ;// 到底下了
     for(int i=1;i<=26;i++){
         int ncnt=cnt+(s[pos]-'a'+1==i);
         int nhash=(hash*b+i)%p;
         if(f[pos+1][ncnt][nhash]) continue;
         f[pos+1][ncnt][nhash]=1;
         dp[pos+1][ncnt][nhash]={pos,cnt,hash,i};
         dfs(pos+1,ncnt,nhash);
     }
}

void print(int pos,int cnt,int hash){
    if(pos==0) return ;
    auto [pos1,cnt1,hash1,u]=dp[pos][cnt][hash];
    print(pos1,cnt1,hash1);
    cout<<char(u+'a'-1);
    if(pos==n) cout<<endl;
}
void solve()
{

    // 我们可以发现总的状态数量并不是很多所以我们直接考虑dfs 来处理同时记录每一个数的状态
    memset(f,0,sizeof f);
    cin>>n>>b>>p>>k;
    b%=p;
    cin>>s;
    int hash=0;
    for(int i=0;i<n;i++){
        hash=(hash*b+(s[i]-'a'+1))%p;
    }
    dfs(0,0,0);
    if(f[n][k][hash])print(n,k,hash);
    else cout<<-1<<endl;
    return ;
}

3.模板分析

   (1)前缀和分析   
      直接求中间这个区间是不可取的复杂的，我们就分成两个从头开始就简单了简单的思维      

   (2)状态定义区间
      int f[N][N];
      第一部分状态的统计 如果说是 要满足某一特性就需要记录下来 比如(连续13，就需记录前后两个位置)
      而对于不要62这种直接被中间剪枝掉的状态是不需要记录的,因为这个维度不会影响,哪些状态是会影响其
      他状态的转移就需要记录下来 比如13你如果不记录的话如果上一次来的数是1 和不是1的可转移的状态是不一样的
      注意空间大下内存使用状态压缩,这个状态需要的不是的话大可不必状态压缩

   (3)dp函数
      取出来每一位进行操作这样就按位来处理一个很大的数

   (4)f初始化问题
      依照题目要求是否需要多次初始化，有时候可以牺牲内存来节省时间维护多次查询的速度

      递归过程承载记录信息的责任我们需要加开一个数组来记录信息考虑数位之间的关系

   (5)dfs的细节
      注意是否会有越界需要剪枝
      流程基本如上分析出每一道题独特的状态之后进行递归(题目需要维护的是什么是不是具有继承性！)
      前导0是否要处理
      对于不需要搜索到底下的数我们可以直接使用快速幂来保证时间复杂度(2023.9.26)

牛客的遇到的题
1.777数
2.22数

状态压缩的结合
1.美丽数
2.学姐的LIS
3.3进制对2进制的优化

二分结合
对于在某一个数内需要满足多少个数的满足要求可以直接使用二分非常的牛逼
启示录

理想化枚举结合
我们需要看如果我们对于dfs的某一个参数无法确定的话,就可以考虑枚举所有的情况
月之迷

字符串结合
百度之星暂无链接
shs在文章中出现3次的方案数,对于其他24个字面我们可以直接简化变成0对于s和h直接简化变成1,2便于我们计算如果以及达到了满足要求的时候我们可以考虑直接结束来保证时间复杂度

#include<bits/stdc++.h> 
using namespace std;
typedef long long LL;
const int N = 1e6+10,mod=1e9+7;

int n;
LL f[N][4][3][3];
LL qmi(LL a,LL b){
    LL res=1;
    while(b){
        if(b&1) res=(LL)res*a%mod;
        b>>=1;
        a=(LL)a*a%mod;
    }
    return res;
}

LL dfs(int pos,int cnt,int last1,int last2){

    LL &v=f[pos][cnt][last1][last2];
    if(!pos) return cnt>=3;// 搜到了最后是可以的解
    if(~v) return v;// 表示被判断过了
    int upper=3;// 上限
    LL res=0;
    for(int i=0;i<upper;i++){
        if((last1==1 && last2==2 && i==1)){// s h s
           if(cnt>=2){
             res+=dfs(pos-1,3,0,0);// 表示更新一手就不能使用了
           }
           else res+=dfs(pos-1,cnt+1,0,0);// 表示更新一手就不能使用了
        }
        else{
            if(!i) res+=24*dfs(pos-1,cnt,last2,i);
            else res+=dfs(pos-1,cnt,last2,i);
        }
        res%=mod;
    }
    res=(res%mod+mod)%mod;
    return v=res;
}

int main( )
{
    memset(f,-1,sizeof f);
    scanf("%d",&n);
    printf("%d",dfs(n,0,0,0));
    return 0;
}

经典存数
给定区间[l,r]我们需要求解在这个区间中的数的数位的最大值和最小值的最小差距的数,我们需要把这个数拿出来

我们可以使用数位dp同时维护这个数即可

// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)// c++ 保留小数\
#define int long long 
typedef long long LL;
typedef pair<int, int> PII;
const int N=1000010,M=1010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
map<int,int> mp;
int t,n,m;
string x,y;
int L[20],R[20];
int pow10[20];


LL f[21][11][11][2][2],g[21][11][11][2][2];


inline int dfs(int pos,int mx,int mi,bool d,bool p){
    int&v=f[pos][mx][mi][d][p];
    if(pos==n+1) return mx-mi;
    if(~v) return v;

    int res=10;

    int l= d ? L[pos] : 0, r = p ?  R[pos] : 9;

    for(int i=l;i<=r;i++){
        int nd =d & i==L[pos],np=p & i==R[pos];
        int ne=dfs(pos+1,max(i,mx),min(mi,i), nd , np);
        if(ne<res){
            res=ne;
            g[pos][mx][mi][d][p]=i*pow10[n-pos]+g[pos+1][max(mx,i)][min(mi,i)][nd][np];
        }
    }
    return v=res;
}
int dp(string x,string y){

    memset(f,-1,sizeof f);
    memset(g,0,sizeof g);
    n=x.size();
    x=' '+x,y=' '+y;
    for(int i=1;i<=n;i++) L[i]=x[i]-'0';
    for(int i=1;i<=n;i++) R[i]=y[i]-'0';
    dfs(1,0,10,1,1);
    return g[1][0][10][1][1];
}

void solve()
{
    cin>>x>>y;
    if(x.size()!=y.size()){
        for(int i=0;i<x.size();i++) cout<<9;
        cout<<endl;
        return ;
    }
    cout<<dp(x,y)<<endl;
    return ;
}
signed main ()
{
    ios// 不能有printf puts scanf
    int t=1;
    pow10[0]=1;
    auto intn = [&] (){
        for(int i=1;i<=18;i++){
            pow10[i]=(LL)pow10[i-1]*10;
        }
    };
    intn();
    cin>>t;
    while(t--){
         solve();
    }
}