1. 全栈程序员必看首页

【算法小讲堂】数位dp（简单入门）

全栈程序员-站长 • • 未分类 • 阅读 2

【算法小讲堂】数位dp（简单入门）数位打牌爷爷 你没有关注的博主又更新博客啦 数位 dp 打牌 这是一个相当深刻的话题 在不会这个内容的时候就是一脸懵逼 这里我们主要介绍的是 dfs 模式实现的数位打牌模式 当然博主也不是说自己会这个高深的算法了 只是看 抄 完别人的代码 突有所悟 又厚颜无耻的出一期博客啦 先来个简单点的问题吧 给出一个数 n 1 n 有多少数不包含 49 测试数据 1 lt T lt 10000 1

数位打牌

爷爷，你没有关注的博主又更新博客啦！！

数位dp（打牌），这是一个相当深刻并且具有意义的话题。在没看懂这个内容的时候完完全全就是一脸懵逼，现在依旧是一脸懵逼。你以为你会了，题目：不，你不会！！就像你可能以为博主已经掌握了这个算法。
欸，你错了，我压根就不会。
　在这里插入图片描述
博主只是看（抄）完别人的代码，突有所悟。又厚颜无耻的出一期博客（瞎bb）！
　　
在这里插入图片描述
好了！今天，在这里，我主要介绍的是dfs模式实现的数位打牌模式 ；先来个简单点的问题吧。












给出一个数n，1~n有多少数包含49，测试数据1<=T<=10000,1<=n<=2^63-1

样例

输出

看完这个，就是下面这表情

在这里插入图片描述
那么我们开始讲讲思路：
　这个问题怎么搞呢，首先我们看到n的范围非常的大，根本没有办法一个一个判断。这时候开动我们的脑袋瓜子，那我们可不可几十个几十个，或者几百个几百个一次算呢?Of course！why not！，这，就是我们打牌数组的来历（dp数组的作用），举个栗子，比如1~500的范围中：1–100，101–200，201–300，都是有一样的个数的符合条件的数字的，因为他们的最高位都与49的4无关，所以这三个区段又与401-500之间的个数不同，综上我们的打牌数组只需要两个维度dp【位数】【最高位是不是4】。接下来就是按从高到低依次枚举就好了。
—-哇，博主，看你这么多，我完全没懂啊！
—-莫慌，先看代码，下面还有讲解。








看代码！接招！

#include 
     using namespace std; const int Max = 99999; const int Min = 0; const int inf = 1e6; const int mod = 1e9+7; #define M 1000 #define N 1000 #define ll long long #define swap(x,y) x^=y^=x^=y ll dp[20][6]; int digit[20]; ll dfs(int pos,int pre,int sta,bool limit){ 
    //以53421为例  if(pos==-1) return 1; //代表这种情况搜索结束，+1  if(!limit&&dp[pos][sta]!=-1) return dp[pos][sta]; //如果没有达到上限比如搜索0--50000 的时候，第一位是0，1，2，3，4的时候没有限制，5的时候有  int up = limit?digit[pos]:9; //有限制的话选取下一位的值，如万位是0，1，2，3，4，千位可以是1-9，但是万位是5，千位不能超过3  ll sum(0); for(int i=0;i<=up;i++){ 
    //每一位进行枚举  if(pre==4&&i==9) continue; //符合条件的不搜了  sum += dfs(pos-1,i,i==4,limit&&i==digit[pos]); //不符合条件的加上，pre记录这一位的值，sta记录是否有可能成为49，最后一个表示是否有限制  } if(!limit) dp[pos][sta] = sum; //没有限制将dp的数值存起来，以便调用  return sum; //返回值  } ll solve(ll a){ 
    int cnt = 0; //分解这个数 while(a>0){ 
    digit[cnt++] = a%10; a/=10; } ll ans = dfs(cnt-1,0,0,true); //对这个数进行dfs return ans; } int main(){ 
    #ifdef LOCAL freopen("test.txt","r",stdin); #endif int T; cin >> T; memset(dp,-1,sizeof(dp)); while(T--){ 
    ll a; scanf("%I64d",&a); ll ans = solve(a); cout << a+1-ans << endl; } return 0; }

在这里插入图片描述

头大啊，这谁顶得住啊！看的我脑阔痛。欸，莫急，看我一一道来

dp数组的作用是什么呢，看这句dp【位数】【最高位是不是4】，dp【20】【2】，一维存储的是每一位（十百千等，这就是我们的存储阶级）中符合条件的个数，比如dp[2][0]存储的就是每一百个数中符合要求的数字数量，dp[2][1]则是400–500中符合要求的数量。为啥要额外计算最高位为4的情况呢，因为400开头，很明显有490-499这一段数是与其他阶段不同的，而且无论题目是49，还是62，道理都是一样的。

因为深搜的特性，在计算dp[4][0]和dp[4][1]的时候（即每一万个数的符合条件的个数）会一口气深搜到底，顺势就得到了4位数以下的数目，因为得到每一万位的时候需要每一千位的值，同样每一千位需要每一百位等等等等。经过存储之后的dp，再经由第15行的返回dp的值，就大大体现了记忆化搜索的好处。

稍微拓展

第45行为啥是＂a+1-ans＂呢？如果题目问50到500之间有多少个这种数怎么办呢？
　 　在这里插入图片描述

问得好！

１.a+1-ans的原因是因为在遍历的时候dfs的内容把０这个数也加了进去，所以ans是比正确答案多１的。
　＋１,－１抵消. 欸，完美，无懈可击！
２.如果，题目问的是50到500之间怎么办！根本不用盘他，开前缀和啊！，solve(50) 记录的是0–50之间的个数，solve(500) 记录的是0–500之间的个数，那么两者相减自然就是 (50,500]（注意这里是开区间）的个数了。如果是【５０，５００】的话就是solve(500)-solve(50-1)。一样的。




好了，这次就到这里了，肝不行了。老板！换肾！！

在这里插入图片描述

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/211262.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月18日 下午10:50
下一篇 2026年3月18日 下午10:50


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号