數(shù)位dp的題目一般會問，某個區(qū)間內(nèi)，滿足某種性質的數(shù)的個數(shù)。

1. 利用前綴和，比如求區(qū)間[l,r]中的個數(shù)，轉化成求[0,r]的個數(shù) [0,l-1]的個數(shù)。
2. 利用樹的結構來考慮（按位分類討論）
   

1081. 度的數(shù)量

#include<bits/stdc++.h>
using namespace std;
const int N=35;
int f[N][N],l,r,K,B;
//預處理組合數(shù)
int init()
{for(int i=0;i<N;i++)for(int j=0;j<=i;j++)if(!j) f[i][j]=1;else f[i][j]=f[i-1][j]+f[i-1][j-1];
}int dp(int n)
{if(!n) return 0;vector<int>vec;while(n) vec.push_back(n%B),n/=B;//十進制轉成B進制int res=0,last=0;//res記錄答案數(shù)，last表示用了多少個1for(int i=vec.size()-1;i>=0;i--){int x=vec[i];//取出第i位數(shù)if(x)//（如果當前位x==0直接進入右分支，討論下一位）{res+=f[i][K-last];//當前位填0，從剩下的所有位（共有i位）中選K-last個數(shù)。//對應于：左分支中0的情況，合法if(x>1){res+=f[i][K-last-1];break;}else//x==1，直接討論下一位，可用的1的個數(shù)減1{last++;if(last>K) break;}}if(i==0&&last==K) res++;//遍歷到最后一位且最后一位取1}return res;
}
int main()
{init();cin>>l>>r>>K>>B;cout<<dp(r)-dp(l-1)<<endl;return 0;
}

1082. 數(shù)字游戲

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int f[N][N],l,r;
//f[i][j]表示一共有i位，且最高位為j的數(shù)的個數(shù)int init()
{for(int j=0;j<=9;j++) f[1][j]=1;for(int i=2;i<N;i++)for(int j=0;j<=9;j++)for(int k=j;k<=9;k++)f[i][j]+=f[i-1][k];
}int dp(int n)
{if(!n) return 1;vector<int>vec;while(n) vec.push_back(n%10),n/=10;int res=0,last=0;//res記錄答案數(shù)，last表示上一位的數(shù)字for(int i=vec.size()-1;i>=0;i--){int x=vec[i];//取出第i位數(shù)if(last>x) break;//這一位數(shù)無論怎么取都比上一位小for(int j=last;j<vec[i];j++)//進入左分支討論res+=f[i+1][j];last=x;//更新latif(!i) res++;//到了最后一位，剩下一種合法的情況}return res;
}
int main()
{init();while(cin>>l>>r)cout<<dp(r)-dp(l-1)<<endl;return 0;
}

1083. Windy數(shù)

#include<bits/stdc++.h>
using namespace std;
const int N=11;
int f[N][N],l,r;
//f[i][j]表示一共有i位，且最高位為j的數(shù)的個數(shù)
//存的是（包含前導零）的情況
int init()
{for(int j=0;j<=9;j++) f[1][j]=1;for(int i=2;i<N;i++)for(int j=0;j<=9;j++)for(int k=0;k<=9;k++)if(abs(j-k)>=2) f[i][j]+=f[i-1][k];
}
int dp(int n)
{if(!n) return 0;vector<int>vec;while(n) vec.push_back(n%10),n/=10;int res=0,last=-2;//res記錄答案數(shù)，last表示上一位的數(shù)字for(int i=vec.size()-1;i>=0;i--){int x=vec[i];//取出第i位數(shù)for(int j=(i==vec.size()-1);j<x;j++)//首位不能取到零，其他位可以if(abs(j-last)>=2) res+=f[i+1][j];if(abs(x-last)>=2) last=x;else break;if(!i) res++;}for(int i=1;i<vec.size();i++)for(int j=1;j<=9;j++)res+=f[i][j];//特判首位為零的情況return res;
}int main()
{init();cin>>l>>r;cout<<dp(r)-dp(l-1)<<endl;return 0;
}

1084. 數(shù)字游戲 II

f[i][j][k] 表示一共有i位，且最高位數(shù)字是j，且所有位數(shù)字和%P結果為k的數(shù)的個數(shù)，若要轉移到f[i][j][k]的狀態(tài)，在i-1位對于每個x（x取值0~9）都應使第三維為(k-j)%P
狀態(tài)轉移方程：
$f[i][j][k]={\sum }_{k=0}^{P?1}{\sum }_{x=0}^{9}f[i?1][x][(k?j)\%P]$

用last表示到當前為止，前面數(shù)位上的數(shù)字之和，對此，當前第i位數(shù)字為j，前面數(shù)字之和為last，那么
后i位(包括j這一位)數(shù)字之和sum與last的關系就是
(last+sum)%N==0,那么sum%N==(-last)%N,
所以res+=f[i+1][j][(-last%N)];

#include<bits/stdc++.h>
using namespace std;
const int N=11;
int f[N][N][110],l,r,P;
//f[i][j][k]表示一共有i位，且最高位數(shù)字是j，且所有位數(shù)字和%P結果為k的數(shù)的個數(shù)
int mod(int u,int v)
{return (u%v+v)%v;
}
int init()
{memset(f,0,sizeof f);for(int i=0;i<=9;i++) f[1][i][i%P]++;for(int i=2;i<N;i++)for(int j=0;j<=9;j++)for(int k=0;k<P;k++)for(int x=0;x<=9;x++)f[i][j][k]+=f[i-1][x][mod(k-j,P)];
}int dp(int n)
{if(!n) return 1;vector<int>vec;while(n) vec.push_back(n%10),n/=10;int res=0,last=0;//res記錄答案數(shù)，last表示前面所有位數(shù)上數(shù)字的和for(int i=vec.size()-1;i>=0;i--){int x=vec[i];    for(int j=0;j<x;j++)  //第i位放0~x-1res+=f[i+1][j][mod(-last,P)]; //0~i位，所以一共有i+1位last+=x;if(!i&&last%P==0) res++;}return res;
}int main()
{while(cin>>l>>r>>P){init();cout<<dp(r)-dp(l-1)<<endl;}return 0;
}

1085. 不要62

#include<bits/stdc++.h>
using namespace std;
const int N=11;
int f[N][N],l,r;
//f[i][j]表示一共有i位，且最高位為j的數(shù)的個數(shù)int init()
{for(int j=0;j<=9;j++) if(j!=4) f[1][j]=1；//一位不含5for(int i=2;i<N;i++)for(int j=0;j<=9;j++){if(j==4) continue;for(int k=0;k<=9;k++){if(k==4||(j==6&&k==2)) continue;f[i][j]+=f[i-1][k];}}
}
int dp(int n)
{if(!n) return 1;vector<int>vec;while(n) vec.push_back(n%10),n/=10;int res=0,last=0;//res記錄答案數(shù)，last表示上一位的數(shù)字for(int i=vec.size()-1;i>=0;i--){int x=vec[i];//取出第i位數(shù)for(int j=0;j<x;j++) {if(j==4||(j==2&&last==6)) continue;res+=f[i+1][j];}if(x==4||(x==2&&last==6)) break;last=x;if(!i) res++;}return res;
}int main()
{init();while(cin>>l>>r,l||r)cout<<dp(r)-dp(l-1)<<endl;return 0;
}