【算法与数据结构】——数位DP（1）

心已赠人 2022-09-10 08:10 235阅读 0赞

# 概念 #

数位DP是与数位相关的一类计数类DP，一般用于统计\[l,r\]区间满足特定条件的元素个数。数位指个位，十位，百位等，数位DP就是在数位上进行动态规划。数位DP在实质上是一种有策略的穷举方式，在子问题求解完毕后将其结果记忆化就可以了。

# 例题1 不要62 #

题目地址[HDU2089 不要62][HDU2089 _62]  
题意：就是给一个n和m求\[n,m\]区间内不含4和62的数字有多少个。  
思路：对于数位DP主要有两种处理方法，一种是预处理方法，一种是记忆化递归

1.  预处理方法  
    首先统计i位数满足条件的元素个数并存储，此题目条件为（不含有不吉利数字62或4），对某一个具体的数进行求解时直接查询结果即可。\[a,b\]区间满足条件的元素个数等于\[1,b\]区间满足条件的元素个数减去\[1，a-1\]区间满足条件的元素个数。  
    状态表示:dp\[i\]\[j\]表示i位数第1个数字是j时满足条件的元素个数。  
    本题的数据位数最多7位，可以预处理9位，预处理只运行一次，只要保证位数比题目中数据大一些就行。  
    状态转移方程如下  
    j=4:dp\[i\]\[j\]=0.第1个数字是4的满足条件的元素个数为0。  
    j=6且k=2:如果第1个数字是6且下一个数字是2，则62是不吉利的数字，不满足条件，不累加；否则枚举下一个数字k，累加dp\[i-1\]\[k\],dp\[i\]\[j\]+=dp\[i-1\]\[k\];k=0,1,…9。  
    临界条件：dp\[0\]\[0\]=1,这样可以保证dp\[1\]\[k\]的值正确  
    预处理代码如下：

void pretreat()
    { 
        dp[0][0] = 1;
        for(int i = 1;i <= 9;i++)
        { 
            for(int j = 0;j <= 9;j++)
            { 
                if(j==4)
                { 
                    dp[i][j] = 0;
                }
                else
                { 
                    for(int k = 0;k <= 9;k++)
                    { 
                        if(j==6&&k==2)
                        { 
                            continue;
                        }
                        dp[i][j] += dp[i-1][k];
                    }
                }
            }
        }
    }

求解区间\[1,x\]区间满足条件的数的个数的过程如下：  
(1) 将整数的各位数字都存储在一个数组中。  
(2) 从高位向低位求解。对每一位i都枚举j=0…num\[i\]-1（这里不能枚举到num\[i\]，因为dp\[i\]\[num\[i\]\]可能会包含大于x的数），如果j=4或j=2且num\[i+1\]=6则不累加，否则and+=dp\[i\]\[j\]。在枚举结果后进行判断，若num\[i\]=4或者num\[i\]=2且num\[i+1\]=6,则ans–（关于ans–的原因在后面说明），同时结束整个循环，因为此时再判断后面的位数已经没有必要了，因为前面的数字已经不满足条件了，到此结束即可。  
代码：

int solve(int x)
    { 
    	int ans = 0,cnt = 0;
        while(x)
        { 
            num[++cnt]=x%10;
            x/=10;
        }
        num[cnt+1] = 0;
        for(int i = cnt;i>=1;i--)
        { 
            for(int j = 0;j <num[i];j++)
            { 
                if(j == 4||(j==2&&num[i+1]==6))
                { 
                    continue;
                }
                else
                { 
                    ans+=dp[i][j];
                }
            }
            if(num[i]==4||(num[i]==2&&num[i+1]==6))
            { 
                ans--;//例如4，统计0,1,2,3共4个，其实只有三个满足，因为我们要求的是[1,x]区间的满足条件的数，因此不能包含0。
                break;
            }
        }
        return ans;
    }

1.  记忆化递归  
    记忆化递归在求解时把中间结果记录下来，若某一项的值已经有解，则直接返回，不需要重新计算，从而大大减少计算量。记忆化递归和动态规划有异曲同工之妙。  
    例如，求解斐波那契数列的记忆化递归算法如下：

long long fac(int n){ 
    	if(f[n]>0)//记忆化递归
    	return f[n];
    	if(n==1||n==2) return f[n]=1;
    	return f[n] = fac(n-1)+fac(n-2);
    }

采用记忆化递归方法求解时的算法设计如下：  
状态表示：dp\[pos\]\[sta\]表示当前第pos位在sta状态满足条件的元素个数,sta表示前一位是否是6，只有0和1两种状态。  
状态转移方程如下：

if(sta&&i==2)continue;
    if(i==4) continue;
    ans+=dfs(pos-1,i==6,limit&&i==len);//dfs(int pos,bool sta,bool limit)

临界条件:若pos=0，则返回1。  
记忆化搜索：若没有限制且已求解，则直接返回，无需递归。  
算法代码：

dfs(int pos,bool sta,bool limit)
    { 
    	if(pos==0) return 1;
    	if(!limit&&dp[pos][sta]!=-1)
    	return dp[pos][sta];
    	int len=limit?a[pos]:9;
    	int ans = 0;
    	for(int i = 0;i <= len;i++)
    	{ 
    		if(sta&&i==2)continue;
    		if(i==4)continue;// 都保证了枚举的合法性
    		ans+=dfs(pos-1,i==6,limit&&i==len);
    	}
    	if(!limit)
    	dp[pos][sta]=ans;
    	return ans;
    }
    int solve(int x)//求解[0,x]区间满足条件的个数
    { 
    	int pos=0;
    	while(x){ 
    		a[++pos]=x%10
    		x/=10;
    	}
    	return dfs(pos,0,1);//若不包括0,则此处减一即可
    }

[HDU2089 _62]: https://acm.hdu.edu.cn/showproblem.php?pid=2089