数位dp第一题

题意：找从n到m中，不包含4，62（连续）的个数

先预处理出f数组     f[i][j]是以j开头的i位数不包含4，62的个数，可通过递推求解

递推关系式为：  f[i][j]=f[i-1][k]+f[i][j];对于第i位，可由第i-1位转移过来，用k枚举第i-1位的所有情况，j枚举第i位的所有情况，这时只需判断i和i-1位不为62，i位不为2的情况

用digit数组来记录从右到左的第i位，然后从最高位（最左边）开始枚举，从0枚举到digit【i】

例如432，这样便列举了所有情况

	4	3	2	4	3	2	4	3	2
枚举	0	枚举到3的取值	枚举到2的取值	4	0	枚举到2的取值	4	3	0
	1	枚举到3的取值	枚举到2的取值	4	1	枚举到2的取值	4	3	1
	2	枚举到3的取值	枚举到2的取值	4	2	枚举到2的取值
	3	枚举到3的取值	枚举到2的取值

如果枚举完之后，保持最大值不变的情况下出现了4，62，则退出，如6231（枚举到3或1的情况时62会保持出现，这种情况要删去）

非递归版本的

#include
      
       #define C 0.5772156649#define pi acos(-1.0)#define ll long long#define mod 1000000007#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;const double g=10.0,eps=1e-7;const int N=10+10,maxn=1000000+10,inf=0x3f3f3f;int f[N][N];//f[i][j]以j开头的i位数不包含4，62的个数int digit[10];//从右到左第i位是多少int getnum(int x){    int len=0,ans=0;    memset(digit,0,sizeof digit);    while(x)    {        digit[++len]=x%10;        x/=10;    }    for(int i=len; i>=1; i--)    {        for(int j=0; j
       
        >n>>m)    {        if(!n&&!m)break;        cout<
        
         <
        
       
      

 递归版本的

#include
      
       #define C 0.5772156649#define pi acos(-1.0)#define ll long long#define mod 1000000007#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;const double g=10.0,eps=1e-7;const int N=20+10,maxn=1000000+10,inf=0x3f3f3f;int dp[N][N],digit[N];int dfs(int len,bool state,bool fp)//state-当前是不是等于6，fp是否访问过{    if(!len)return 1;    if(!fp&&dp[len][state]!=-1)return dp[len][state];    int ret=0,fpmax=fp ? digit[len] : 9;    for(int i=0;i<=fpmax;i++)    {        if(i==4||state&&i==2)continue;        ret+=dfs(len-1,i==6,fp&&i==fpmax);    }    if(!fp)dp[len][state]=ret;    return ret;}int solve(int x){    int len=0;    while(x)    {        digit[++len]=x%10;        x/=10;    }    return dfs(len,0,1);}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int a,b;    memset(dp,-1,sizeof dp);    while(cin>>a>>b)    {        if(a==0&&b==0)break;        cout<
       
        <
       
      

发现网上的代码关于数位dp的几乎都是递归写的，所以还是找递归版本理解比较好