数位dp(算法篇)
算法篇之数位dp
数位dp
概念：
数位dp是一种计数用的dp，一般是要统计一个区级[l,r]内满足一些条件的数的个数- 所谓数位dp，就是对数位进行dp，也就是个位、十位等
- 相对于普通的暴力枚举，数位dp快就快在它的记忆化，也就是说后面可能会利用到前面已经计算好的东西
- 题型往往是：给定一个闭区间[L,R]，求这个区间中满足"某种条件"的数的总数量
题型特征：
- 要求统计满足一定条件的数的数量（即，最终目的为计数）；
- 这些条件经过转化后可以使用「数位」的思想去理解和判断；
- 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
- 上界很大（比如1018），暴力枚举验证会超时。
总结：给定一个闭区间[L,R]，求这个区间中满足"某种条件"的数的总数量
基本原理：
考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。，而我们的统计就是由记忆化搜索解决
具体实现：
-
数位dp首先通常把统计[L,R]范围内满足条件的数字转化为统计[1,N]内满足条件的数字数量，这样就将下界限制去掉,只考虑上边界。就变成：
Ans[L,R]=Ans[1,R]-Ans[1,L-1] -
将数字大小转换为数位字典序，也就是记录最大枚举到的数字每一位的数值(例如R为123456，那word[1]=6,word[2]=5依次类推)。我们称这个数组为
word[n+1] -
DFS要记录的状态:
- 现在枚举到哪一位，记为
pos - 前面一位的数字是多少，记为
pre - 这一位可以填的最大数字，记为
up，但是求解过程我们会以flag来表示是否需要更新up
- 现在枚举到哪一位，记为
-
我们开始从最高位到最低位枚举，对于当前位置x有两种填补可能性：
- 如果
x前面某一位已经小于对应位置的上限数字，则这一位可以填0-9 - 如果
x前面每一位都等于对应位置的上限数字，这一位可填数字范围为0-x对应位置的上限数字
所以，我们只需要维护前面每一位数字是否和上限数字一样，就可以得到这个位置数字可填范围
- 如果
-
如果
flag为false，那么dfs计算的过程就和up毫无关系，那么我们可以考虑把这个状态答案记录下来，用于后面复用
模板：
//pos为当前位数
//pre代表前一位所填数字
//flag代表前面每一位数字是否都等于对应的上限数字
int dfs(int pos,int pre,bool flag){
//如果pos<=0表示枚举完每一位，那返回对应要返回的值
if(pos<=0) return 需要返回值;
//如果该状态已经计算过了就返回
if(!flag&&dp[pos][pre]!=-1) return dp[pos][pre];
//如果flag为true，up就为对应的上限数字，反之就为9
int up=flag?word[pos]:9;
int cnt=0; //计数
for(int i=0;i<=up;++i){
if(判断数位是否满足条件) cnt+=dfs(pos-1,i,flag&&(i==up)); //如果满足就继续搜索
}
//记录状态
if(!flag) dp[pos][pre]=cnt;
return cnt;
}
例题：
-
Windy数：定义不含前导0且相邻两个数字之差至少为2的正整数被称为windy数，比如5，36，192都是windy数，10，21不是windy数，求[L,R]范围内有多少个Windy数，1<=L,R<=1e18;#include <bits/stdc++.h> using namespace std; typedef long long ll; ll word[20]; ll dp[30][10]; //lead是用来判断前面一位是否为0 ll dfs(ll pos,ll pre,bool flag,bool lead){ if(pos<=0) return 1; //因为不含前导0，所以pre要大于0 if(!flag&&pre>0&&dp[pos][pre]!=-1) return dp[pos][pre]; int up=flag?word[pos]:9; ll cnt=0; for(int i=0;i<=up;++i){ //因为要求不含前导0，所以当前面一位为0，说明这一位就为数的开始，所以算是符合条件 if(abs(i-pre)>=2||lead) cnt+=dfs(pos-1,i,flah&&(i==up),lead&&(i==0)); } if(!flag) dp[pos][pre]=cnt; return cnt; } ll solve(ll x){ int pos=0; memset(dp,-1,sizeof dp); while(x){ word[++pos]=x%10; x/=10; } return dfs(pos,0,1,1); } int main(){ ll a,b; while(cin>>a>>b) cout<<solve(b)-solve(a-1)<<endl; return 0; } -
统计整数数目：
class Solution {
public:
int min_sum,max_sum;
int dp[23][401];
char word[25];
const int mod=1e9+7;
int dfs(int pos,int sum,bool flag){
if(pos<=0) return sum>=min_sum;
if(!flag&&dp[pos][sum]!=-1) return dp[pos][sum];
int up=flag?word[pos]-'0':9;
int res=0;
for(int i=0;i<=up;++i){
if(sum+i<=max_sum) res=(res+dfs(pos-1,sum+i,flag&&(i==up)))%mod;
}
if(!flag) dp[pos][sum]=res;
return res;
}
int solve(string x){
int pos=0;
for(int i=x.size()-1;i>=0;--i) word[++pos]=x[i];
return dfs(pos,0,1);
}
int count(string num1, string num2, int min_sum, int max_sum) {
int n=num1.size()-1;
while(num1[n]=='0'){
num1[n]='9';
n--;
}
num1[n]--;
memset(dp,-1,sizeof dp);
this->min_sum=min_sum;
this->max_sum=max_sum;
return (solve(num2)-solve(num1)+mod)%mod;
}
};
原文地址：https://blog.csdn.net/hellmorning/article/details/142448596
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！