数位dp：一种计数用的dp，一般就是要统计一个区间[l,r]内满足一些条件数的个数，通常情况下l和r都比较大。所谓数位dp，字面意思就是在数位上进行dp。数位型dp的核心思想是在数位上不进行暴力搜索，而是采取记忆化搜索的形式，然后进行求值。经典题目1：一个数位上的数位型dp。题目：在 1 至 n 中，有多少个数的数位中包含数字 9？参考代码：
#include<bits/stdc++.h>
using namespace std;
int dfs(vector<int>& dp,vector<int>&dig,int pos,bool flag){
if(pos<0) return 1;
if(!flag&&dp[pos]!=-1) return dp[pos];
int mx=flag?dig[pos]:9;
int res=0;
for(int i=0;i<=mx;i++){
if(i!=9){
res+=dfs(dp,dig,pos-1,flag&&i==dig[pos]);
}
}
if(!flag) dp[pos]=res;
return res;
}
int main()
{
int n;
vector<int> dig;
cin>>n;
int t=n;
while(t){
dig.push_back(t%10);
t=t/10;
}
vector<int> dp(dig.size(),-1);
cout<<n-dfs(dp,dig,dig.size()-1,true)+1;
return 0;
}
经典题目2：在 1 至 n 中，有多少个数的数位中包含数字 62或者4？ //做法和上面差不多相同参考代码：
#include<bits/stdc++.h>
using namespace std;
int dfs(vector<vector<int>>& dp,vector<int>&dig,int pos,bool sta,bool flag){
if(pos<0) return 1;
if(!flag&&dp[pos][sta]!=-1) return dp[pos][sta];
int mx=flag?dig[pos]:9;
int res=0;
for(int i=0;i<=mx;i++){
if(i==4) continue;
if(sta&&i==2) continue;
res+=dfs(dp,dig,pos-1,i==6,flag&&i==dig[pos]);
}
if(!flag) dp[pos][sta]=res;
return res;
}
int main()
{
int n;
vector<int> dig;
cin>>n;
int t=n;
while(t){
dig.push_back(t%10);
t=t/10;
}
vector<vector<int>> dp(dig.size(),vector<int>(2,-1));
cout<<n-dfs(dp,dig,dig.size()-1,0,true)+1;
return 0;
}
经典题目3：不含前导零且相邻两个数字之差至少为 2的正整数被称为 windy 数。windy 想知道，在 aa 和 bb 之间，包括 aa 和 bb ，总共有多少个 windy 数？参考代码：
#include<bits/stdc++.h>
using namespace std;
const int N=20;
long long dp[N][2][10];
int dig[N];
long long dfs(int pos,int pre,int zero,bool flag){
if(pos<0) return 1;
if(!flag&&dp[pos][zero][pre]!=-1) return dp[pos][zero][pre];
int mx=flag?dig[pos]:9;
long long res=0;
for(int i=0;i<=mx;i++){
if(zero||abs(pre-i)>=2){
res+=dfs(pos-1,i,zero&&!i,flag&&i==dig[pos]);
}
}
if(!flag) dp[pos][zero][pre]=res;
return res;
}
long long solve(long long x){
int sz=0;
while(x){
dig[sz++]=x%10;
x=x/10;
}
return dfs(sz-1,0,1,true);
}
int main()
{
memset(dp,-1,sizeof(dp));
long long n,m;
cin>>n>>m;
cout<<solve(m)-solve(n-1);
return 0;
}
经典题目4：求一段区间内的二进制0的个数不少于1的个数的数的数量。参考代码：
#include<bits/stdc++.h>
using namespace std;
const int N=70;
long long dp[N][N][N];
int dig[N];
long long dfs(int pos,int num0,int num1,int zero,bool flag){
if(pos<0) return num0>=num1;
if(!flag&&dp[pos][num0][num1]!=-1)
return dp[pos][num0][num1];
int mx=flag?dig[pos]:1;
long long res=0;
for(int i=0;i<=mx;i++){
if(i==0){
res+=dfs(pos-1,num0+zero?0:1,num1,zero,flag&&i==dig[pos]);
}else{
res+=dfs(pos-1,num0,num1+1,0,flag&&i==dig[pos]);
}
}
if(!flag)
dp[pos][num0][num1]=res;
return res;
}
long long solve(long long x){
int sz=0;
while(x){
dig[sz++]=x%2;
x=x/2;
}
return dfs(sz-1,0,0,1,true);
}
int main()
{
memset(dp,-1,sizeof(dp));
long long n,m;
cin>>n>>m;
cout<<solve(m)-solve(n-1);
return 0;
}
经典题目5：给两个数A,B，给一个定义：X的十进制表示为AnAn-1An-2…A2A1,f(x)=An* pow(2,n-1)+An-1* pow(2,n-2)+…+A2* 2+A1*1,请问0-B有多少f(x)<=f(A)的数的个数参考代码：
#include<bits/stdc++.h>
using namespace std;
const int N=70;
const int M=10005;
long long dp[N][M];
int dig[N];
long long f(int x){
long long mul=1;
long long res=0;
while(x){
res+=(x%10)*mul;
mul=mul<<1;
x=x/10;
}
return res;
}
long long dfs(int pos,long long sub,bool flag){
if(sub<0) return 0;
if(pos<0) return sub>=0;
if(!flag&&dp[pos][sub]!=-1)
return dp[pos][sub];
int mx=flag?dig[pos]:9;
long long res=0;
for(int i=0;i<=mx;i++){
res+=dfs(pos-1,sub-i*(1<<pos),flag&&i==dig[pos]);
}
if(!flag)
dp[pos][sub]=res;
return res;
}
long long solve(long long x,long long k){
int sz=0;
while(x){
dig[sz++]=x%10;
x=x/10;
}
return dfs(sz-1,k,true);
}
int main()
{
memset(dp,-1,sizeof(dp));
long long n,m;
cin>>n>>m;
long long k=f(n);
cout<<solve(m,k);
return 0;
}
经典题目6：给定一个int类型能够保存的整数n，求1~n中能被13整除而且包含13的数字的个数。例如13、2613等。思路：数位d，这里需要单开一维记录第k位之前的数字除以13的余数。即dfs的mod参数。pre参数的意义：前一位是哪一个。sta表示前面是否出现过13.参考代码：
#include<bits/stdc++.h>
using namespace std;
const int N=70;
long long dp[N][15][2][10];
int dig[N];
long long dfs(int pos,int mod,int pre,bool sta,bool flag){
if(pos<0){
return sta&&mod%13==0;
}
if(!flag&&dp[pos][mod][sta][pre]!=-1)
return dp[pos][mod][sta][pre];
int mx=flag?dig[pos]:9;
long long res=0;
for(int i=0;i<=mx;i++){
res+=dfs(pos-1,(10*mod+i)%13,i,sta||(pre==1&&i==3),flag&&i==dig[pos]);
}
if(!flag)
dp[pos][mod][sta][pre]=res;
return res;
}
long long solve(long long x){
int sz=0;
while(x){
dig[sz++]=x%10;
x=x/10;
}
return dfs(sz-1,0,-1,false,true);
}
int main()
{
memset(dp,-1,sizeof(dp));
long long n;
cin>>n;
cout<<solve(n);
return 0;
}
经典题目7：定义平衡数，以概述某一位为原点，原点两侧所有的数位的扭矩相等，某一个数位的扭矩等于该数位的值乘以该数位的值乘以该数位到原点的距离，如4139如果以3为原点，左边扭矩和为42+11，右边扭矩为9*1，求一个区间内平衡数的个数。参考代码：
#include<bits/stdc++.h>
using namespace std;
const int N=70;
long long dp[N][N][150*N];
int dig[N];
long long dfs(int pos,int center,long long s,bool flag){
if(s<0) return 0;
if(pos<0) return s==0;
int mx=flag?dig[pos]:9;
if(!flag&&dp[pos][center][s]!=-1) return dp[pos][center][s];
long long res=0;
for(int i=0;i<=mx;i++){
res+=dfs(pos-1,center,s+i*(pos-center),flag&&i==dig[pos]);
}
if(!flag) dp[pos][center][s]=res;
return res;
}
long long solve(long long x){
int pos=0;
while(x){
dig[pos++]=x%10;
x=x/10;
}
long long res=0;
for(int i=0;i<pos;i++){
res+=dfs(pos-1,i,0,true);
}
return res-(pos-1);
}
int main()
{
memset(dp,-1,sizeof(dp));
long long n;
cin>>n;
cout<<solve(n);
return 0;
}
Processed:
0.010, SQL:
8
