标签：int dp pos zero DP define 模板 数位

数位DP：

一般来说数位DP有两种写法：1.for循坏枚举DP 2.记忆化搜索+DP

这里详细将记忆化搜索+DP

DFS状态：

常见的dfs状态有三个：

1.枚举到第几位（POS）

2.判断前面是否紧贴上限（LIMIT）

3.前面的数是否全为前导0 （ZERO）

 

这三个状态如何转移到下一位呢？

1.pos→pos+1

2.limit→limit&&a[i]=当前这位最高位

3.zero→zero&&a[i]=0

 

重点：dfs的核心是深搜，一搜搜到底,搜到底了，代表我们搜完了一个数，return 1；

 

 

 

现在问有多少的数比12345小

1.关于前导0：00999→999，09999→9999

2.关于limit前面的数是否紧贴上限

如果前面的数是紧贴上限的，当前这位枚举的上限便是当前数的上限

如果前面的数不是紧贴上限的，当前这位枚举的上限便是 9

3.关于记忆化DP

现在枚举到了 10××× 和 11×××

显然 这两种状态后面的×××状态数是一样的，我们只用枚举一次，再碰到直接return值就好了

4.关于DP维度

一般来说，DFS有几个状态，DP就几个维度　　

比如现在DP就是DP [pos] [limt] [zero] 

5.关于DP细节

一般来说我们一开始都memset(dp,-1,sizeof(dp))

如果dp[pos][limt][zero]!=-1 return dp[pos][limit][zero];

6.关于初始化：

一开始 limit 是1，表示一开始的数只能选 1~a[1]

一开始zero 是1，假定表示前面的数全为0

 

最后放个数位DP模板:（询问 L~R 之间有多少的数）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   //vector函数
#define popb pop_back  //vector函数
#define fi first
#define se second
const int N=20;
//const int M=;
//const int inf=0x3f3f3f3f;     //一般为int赋最大值,不用于memset中
//const ll INF=0x3ffffffffffff; //一般为ll赋最大值,不用于memset中
int T,n,len,a[N],dp[N][2][2];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int dfs(int pos,bool lim,bool zero)
{
    if(pos>len) return 1;
    if(dp[pos][lim][zero]!=-1) return dp[pos][lim][zero];
    int res=0,num=lim?a[pos]:9;
    for(int i=0;i<=num;i++)
        res+=dfs(pos+1,lim && i==num,zero && i==0 );
    return dp[pos][lim][zero]=res; 
} 
int solve(int x)
{
    len=0;
    memset(dp,-1,sizeof(dp));
    for(;x;x/=10) a[++len]=x%10;
    reverse(a+1,a+len+1);
    return dfs(1,1,1);
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);    
    int l=read(),r=read();
    printf("%d\n",solve(r)-solve(l-1));
    return 0;
}

 

标签：int,dp,pos,zero,DP,define,模板,数位
From： https://www.cnblogs.com/Willette/p/17066100.html