首页 > 代码库 > 数位dp模版（dp）
数位dp模版（dp）
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 6 using namespace std; 7 8 int t; 9 long long dp[19][19][2005];10 long long l, r;11 int shu[20];12 13 long long dfs(int len,..., bool shangxian)14 {15 if (len == 0)16 return ...;17 if (!shangxian && dp[len][...])18 return dp[len][...]; //dp数组的内容应和dfs调用参数的内容相同，除了是否达到上限19 long long cnt = 0;20 int maxx = (shangxian ? shu[len] : 9);21 for (int i = 0; i <= maxx; i++)22 {23 ...;24 cnt += dfs(len - 1,..., shangxian && i == maxx);25 }26 if (!shangxian)27 dp[len][...] = cnt;28 return cnt;29 }30 31 long long solve(long long x)32 {33 int k = 0;34 while (x)35 {36 shu[++k] = x % 10;37 x /= 10;38 }39 return dfs(k,...,1)40 }41 42 int main()43 {44 memset(dp, 0, sizeof(dp));45 scanf("%lld%lld", &l, &r); //有些题目其实并不需要用到long long46 printf("%lld\n", solve(r) - solve(l - 1)); //只有满足区间减法才能用47 48 //while (1);49 return 0;50 }
数位dp是一种计数用的dp，一般就是统计一个区间[l,r]内满足一些条件数 的个数，所谓数位dp，字面意思就是在数位上dp。数位的含义：一个数有个位，十位，百位，千位···数的每一位就是数位。
之所以要引入数位的概念完全就是为了dp。数位dp的实质就是换一种暴力枚举的方式，使新的枚举方式满足dp的性质，然后记忆化即可。
两种不同的枚举：对于一个求区间[l,r]满足条件数的个数，最简单的暴力如下：
for(int i=l;i<=r;i++) if(right(i)) ans++;
然而这样枚举不方便记忆化，或者根本无状态可言。
数位dp模版（dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。