殡葬网站建设_网页设计作品集展示_杭州seo排名收费_长尾词挖掘

算法篇之数位dp

数位dp

概念：

• 数位dp是一种计数用的dp，一般是要统计一个区级[l,r]内满足一些条件的数的个数
• 所谓数位dp，就是对数位进行dp，也就是个位、十位等
• 相对于普通的暴力枚举，数位dp快就快在它的记忆化，也就是说后面可能会利用到前面已经计算好的东西
• 题型往往是：给定一个闭区间[L,R]，求这个区间中满足"某种条件"的数的总数量

题型特征：

1. 要求统计满足一定条件的数的数量（即，最终目的为计数）；
2. 这些条件经过转化后可以使用「数位」的思想去理解和判断；
3. 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
4. 上界很大（比如10¹⁸），暴力枚举验证会超时。

总结：给定一个闭区间[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要记录的状态:

  1. 现在枚举到哪一位，记为pos
  2. 前面一位的数字是多少，记为pre
  3. 这一位可以填的最大数字，记为up，但是求解过程我们会以flag来表示是否需要更新up

• 我们开始从最高位到最低位枚举，对于当前位置x有两种填补可能性：

  1. 如果x前面某一位已经小于对应位置的上限数字，则这一位可以填0-9
  2. 如果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就为对应的上限数字，反之就为9int 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;
}

例题：

1. 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要大于0if(!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;
   }
   

2. 统计整数数目：

   

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;}
};