基础
对于一类问题：求给定区间内，满足给定条件的数的个数。一般情况下，这类问题通常采用暴力枚举求解：
for(int i=l;i<=r;++i) if(right(i)) ++ans;
很显然，当给定区间过大时，无法直接用朴素的方法求解。而所求的限定条件往往与数位有关，例如数位之和、指定数码个数、数的大小顺序分组等等。此时我们就需要利用数位的性质，设计log级别复杂度的算法。
解决这类问题最基本的思想就是“逐位确定”，有时求解这类问题时还需要做预处理，而预处理的过程即可视作数位dp。
简单而言，数位dp就是在给定的区间内，利用限定条件，逐位暴力枚举的算法。
对于数位dp，可通过简单的分析进行了解。
我们假设给定一个r=312。对于数位dp的过程，也就是从最高位即百位起，顺次枚举0-9。
但是很显然，以百位3为例，枚举时数字最大不能超过3。同时当百位为3时，十位最大不能超过1；当百位为3，十位为1时，个位最大不能超过2。其他限定情况下也以此类推。所以在实际的运用中，需要用一个布尔变量limit记录这一情况。
另一方面，数位dp中，对于问题的求解，通常是：
printf("%dn",solve(l)-solve(r-1));
所以不管左端点是多少，百位一定会枚举到0，可是这样前导零可能会影响计数（视题目而定），所以通常情况下还会用一个布尔变量lead记录具体情况。
lead和limit一样，当前面已经不存在前导零or最大值限定时，是不必再继续限定的。
这样就得到了数位dp最基本的模板：
int dfs(int pos,int sta,bool lead,bool limit) //pos即枚举到的位数；sta起到记录作用，一般情况下是记录上一位的数值，也有可能根据题意记录如4的个数5的个数 //lead记录前导零；limit记录数值的限定 { if(pos==-1) return 1;//也就是位数由大到小枚举退出的边界 if(!limit&&!lead&&dp[pos][sta]!=-1) return dp[pos][sta];//情况已经记录时返回，节省时间 int up=limit?a[pos]:9,ans=0;//确定可枚举到的最大数 for(int i=0;i<=up;++i) { //判断条件 } if(!limit&&!lead) dp[pos][sta]=ans;//记忆化，存储节省时间 return ans; } int solve(int x) { int pos=0; while(x) { a[pos++]=x%10; x/=10; }//确定每一位的最大值限定 return dfs(pos-1,-1,true,true); } int main() { memset(dp,-1,sizeof(dp)); int a,b; scanf("%d%d",&a,&b); printf("%dn",solve(b)-solve(a-1)); }
要注意的是，dfs的四个变量并不一定会用到，也有可能更多，视情况而定。
同时，solve中的拆分也可能是二进制的情况。
例题
例题1 scoi2009 windy数
比较典型的数位dp例题，要注意前导零的情况，可以直接套板子。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int a[15],dp[15][15]; int dfs(int pos,int sta,bool lead,bool limit) { if(pos==-1) return 1; if(!limit&&!lead&&dp[pos][sta]!=-1) return dp[pos][sta]; int up=limit?a[pos]:9,ans=0; for(int i=0;i<=up;++i) { if(!lead&&abs(i-sta)<2) continue; if(lead&&i==0) ans+=dfs(pos-1,sta,lead,limit&&i==a[pos]); else ans+=dfs(pos-1,i,lead&&i==0,limit&&i==a[pos]); } if(!limit&&!lead) dp[pos][sta]=ans; return ans; } int solve(int x) { int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dfs(pos-1,-1,true,true); } int main() { memset(dp,-1,sizeof(dp)); int a,b; scanf("%d%d",&a,&b); printf("%dn",solve(b)-solve(a-1)); }
例题2 poj 3252 round numbers
这里就要注意sta存储的不再是上一位的值而是0比1多的值，但是因为可能会出现0比1少也就是负数的情况，而数组下标不能是负数，所以初始值就要根据题目设为32。
又因为是二进制，所以solve也会有一定的更改。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int st,ed; int a[35],dp[35][70]; int dfs(int pos,int sta,bool lead,bool limit) { if(pos==-1) return sta>=32; if(!lead&&!limit&&dp[pos][sta]!=-1) return dp[pos][sta]; int up=limit?a[pos]:1,ans=0; for(int i=0;i<=up;++i) { if(lead&&i==0) ans+=dfs(pos-1,sta,lead,limit&&i==a[pos]); else ans+=dfs(pos-1,sta+(i==0?1:-1),lead&&i==0,limit&&i==a[pos]); } if(!lead&&!limit) dp[pos][sta]=ans; return ans; } int solve(int x) { int pos=0; while(x) { a[pos++]=x&1; x>>=1; } return dfs(pos-1,32,true,true); } int main() { memset(dp,-1,sizeof(dp)); scanf("%d%d",&st,&ed); printf("%d",solve(ed)-solve(st-1)); return 0; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/602245.html