脚本宝典收集整理的这篇文章主要介绍了数位DP，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

数位dp

特点：

1. 数据范围贼大
2. (O(n)) 算法绝对不行
3. 看上去很套路，统计各种数在序列中出现的个数或者之类的。

引入：

数位 (dp) 解决的是什么问题呢？

一般来说：求出在给定区间中，符合条件 (f(i)) 的数 (i) 的个数，条件 (f(i)) 一般和数的大小没关系，和数的组成有关。

数的大小对复杂度的影响很小。

设计搜索

利用记忆化搜索。

一.记忆化搜索过程：

对于 ([l,r]) 区间，我们转化成 ([1,l],[1,r]) 区间求解/

从起点向下搜索，到最底层得到方案数，一层一层返回答案，累计到起点即得到答案。

二.状态设计：

我们思考一下 (DFs) 过程中需要哪些参数？

1. 数字位数 (pos) ,记录答案的 (sum),最高位限制 (limIT)
2. 我们还需要一个判断前导 (0) 的标记 (lead)
3. 数位 (dp) 解决的是数字组成问题，因此要记录一下前几位 (PRe),方便比较。
4. 又还需要其他参量，根据题意设置。

总结一句话：数位 (dp) 的状态能记录的就都记录上。

分析细节：

一.前导零标记 (lead):

由于我们要搜索的数字很长，所以我们需要从最高位开始搜。

举个例子：假如我们要从 ([0,1000]) 找任意相邻两数相等的数：

显然 (111,222,888) 等等是符合题意的数。

但是我们发现右端点 (1000) 是四位数。

因此我们搜索的起点是 (0000)，而三位数的记录都是 (0111,0222,0888) 等.

而这种情况下如果我们直接找相邻位相等则 (0000) 符合题意而 (0111,0222,0888) 都不符合题意了

所以我们要加一个前导 (0) 标记

如果当前位 (lead=1) 而且当前位也是 (0) ，那么当前位也是前导 (0) ，(pos+1) 继续搜；

如果当前位 (lead=1) 但当前位不是 (0)，则本位作为当前数的最高位，(pos+1) 继续搜；（注意这次根据题意 (sum) 或其他参数可能发生变化）

如果是关于数字的结构，那么需要记录前导零，如果只是组成的话，前导零并不影响我们的判断。

二.最高位标记 (limit):

我们知道在搜索的数位搜索范围可能发生变化：

举个例子：我们在搜索 ([0,555]) 的数时，显然最高位搜索范围是 ([0,5])，而后面的位数的取值范围会根据上一位发生变化：

1. 当最高位是 ([1,4]) 时，第二位取值为 ([0,9]);
2. 当最高位是 (5) 时，第二位取值为 ([0,5]) （再往上取就超出右端点范围了）

为了分清这两种情况，我们引入了 (limit) 标记：

1. 若当前位 (limit=1) 而且已经取到了能取到的最高位时，下一位 (limit=1)；
2. 若当前位 (limit=1) 但是没有取到能取到的最高位时，下一位 (limit=0)；
3. 若当前位 (limit=0) 时，下一位 (limit=0) 。

我们设这一位的标记为 (limit) ，这一位能取到的最大值为 (res)，则下一位的标记就是 (i==res&&limit) （(i)枚举这一位填的数）

三.(dp) 值的记录和使用

最后我们考虑 (dp) 数组下标记录的值

本文介绍数位 (dp) 是在记忆化搜索的框架下进行的，每当找到一种情况我们就可以这种情况记录下来，等到搜到后面遇到相同的情况时直接使用当前记录的值。

(dp) 数组的下标表示的是一种状态，只要当前的状态和之前搜过的某个状态完全一样，我们就可以直接返回原来已经记录下来的 (dp) 值。

举个例子：

假如我们找 ([0,123456]) 中符合某些条件的数

假如当我们搜到 (1000??) 时，(dfs) 从下返上来的数值就是当前位是第 (5) 位，前一位是 (0) 时的方案种数，搜完这位会向上反，这是我们可以记录一下：当前位第 (5) 位，前一位是 (0) 时，有这么多种方案种数.

当我们继续搜到 (1010??) 时，我们发现当前状态又是搜到了第 (5) 位，并且上一位也是 (0)，这与我们之前记录的情况相同，这样我们就可以不继续向下搜，直接把上次的 (dp) 值返回就行了。

注意，我们返回的 (dp) 值必须和当前处于完全一样的状态，这就是为什么 (dp) 数组下标要记录 (pos,pre) 等参量了。

但是否所有情况都是这样满足呢？答案是否定的。

接着上面的例子，范围 ([0,123456])

如果我们搜到了 (1234??)，我们能不能直接返回之前记录的：当前第 (5) 位，前一位是 (4) 时的 (dp) 值？

我们发现，这个状态的 (dp) 值被记录时，当前位也就是第 (5) 位的取值是 ([0,9])，而这次当前位的取值是 ([0,5])，方案数一定比之前记录的 (dp) 值要小。

当前位的取值范围为什么会和原来不一样呢？

如果你联想到了之前所讲的知识，你会发现：现在的 (limit=1)，最高位有取值的限制。

因此我们可以得到一个结论：当 (limit=1) 时，不能记录和取用 (dp) 值！

类似上述的分析过程，我们也可以得出：当 (lead=1) 时，也不能记录和取用 (dp) 值！

模板：

ll dfs(int pos,int pre,int sum,……,int lead,int limit){
    if(pos>len) return sum;//剪枝
    if((dp[pos][pre][sum]……[……]!=-1&&(!limit)&&(!lead))) return dp[pos][pre][sum]……[……];//记录当前值
    ll ret=0;//暂时记录当前方案数
    int res=limit?a[len-pos+1]:9;//res当前位能取到的最大值
    for(int i=0;i<=res;i++){
        //有前导0并且当前位也是前导0
        if((!i)&&lead) ret+=dfs(……,……,……,i==res&&limit);
        //有前导0但当前位不是前导0，当前位就是最高位
        else if(i&&lead) ret+=dfs(……,……,……,i==res&&limit); 
        else if(根据题意而定的判断) ret+=dfs(……,……,……,i==res&&limit);
    }
    if(!limit&&!lead) dp[pos][pre][sum]……[……]=ret;//当前状态方案数记录
    return ret;
}
ll part(ll x){//把数按位拆分
    len=0;
    while(x) a[++len]=x%10,x/=10;
    memset(dp,-1,sizeof dp);//初始化-1（因为有可能某些情况下的方案数是0）
    return dfs(……,……,……,……);//进入记搜
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld",&l,&r);
        if(l) printf("%lld",part(r)-part(l-1));//[l,r](l!=0)
        else printf("%lld",part(r)-part(l));//从0开始要特判
    }
    return 0;
}

例题：

P6218 [USACO06NOV] Round Numbers S

题意：

给定区间 ([l,r]) ，求出区间内每个数在二进制表示下 (0) 的个数不小于 (1) 的个数的 数的 数量。

这道题几乎就是数位 (dp) 的模板题：我们只需要判断在 ([1,l-1]) 和 ([1,r]) 的长度下计算，然后容斥就可以。

接下来是代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int l,r;
int a[50],len,f[105][105],vis[105][105];
int dfs(bool limit,bool lead,int pos,int cha){
    if(pos==0) return cha>=30;//0比1多返回 1，否则返回0，一开始初始是30（考虑到会成负数的情况） 
    if(!limit&&!lead&&vis[pos][cha]) return f[pos][cha];
    int res=0,top=limit?a[pos]:1;
    for(int i=0;i<=top;i++){
        res+=dfs(limit&(i==a[pos]),lead&(i==0),pos-1,cha+(i==0?(lead?0:1):-1));
    }
    if(!limit&&!lead) vis[pos][cha]=1,f[pos][cha]=res;
    return res;
}
int solve(int x){
    for(len=0;x;x/=2) a[++len]=x%2;
    return dfs(1,1,len,30);
}
int main()
{
    cin>>l>>r;
    cout<<solve(r)-solve(l-1)<<endl;
    System("pause");
    return 0;
}

P2602 [ZJOI2010]数字计数

这道题同样也算是一道模板题：

题意：

计算 ([l,r]) 区间内 (0-9) 出现的个数。

这道题也算是比较好做，我们只需要对于 (0——9) 进行枚举，在 (dfs) 中传一个变量来表示当前要搜索的值，进行搜索就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll l,r;
ll dp[105][105][2][2],len,a[105];
ll dfs(bool limit,bool lead,int pos,int sum,int now){
    if(pos==0) return sum;
    if(dp[pos][sum][limit][lead]!=-1) return dp[pos][sum][limit][lead];
    ll res=0,top=limit?a[pos]:9;
    for(int i=0;i<=top;i++){
        res+=dfs(limit&(i==a[pos]),lead&(i==0),pos-1,sum+((!lead||i)&&(i==now)),now);
    }
    dp[pos][sum][limit][lead]=res;
    return res;
}
ll calc(ll x,int now){
    for(len=0;x;x/=10) a[++len]=x%10;
    memset(dp,-1,sizeof(dp));
    return dfs(1,1,len,0,now);
}
int main()
{
    cin>>l>>r;
    for(int i=0;i<10;i++){
        cout<<calc(r,i)-calc(l-1,i)<<" ";
    }
    cout<<endl;
    system("pause");
    return 0;
}

总结：

1. 数位 (dp) 要想做好，最重要的就是 (dfs) 状态的设计。一般来说，需要用到位运算和前导零之类的数据。只要我们设计好状态转移，数位 (dp) 这个看上去玄学的东西都是比较好解决的。

2. 如果遇到数位相加，可以把一个数看成 (9) 个以内若干个 (1) 的后缀相加而成。

脚本宝典总结

以上是脚本宝典为你收集整理的数位DP全部内容，希望文章能够帮你解决数位DP所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。