数位DP是用记忆化搜索做的。个人觉得比较难理解。很对函数中的参数比如前导零什么意思也没有说明，所以导致难以学习。
记忆化搜索dfs(int len,int pre,int limit); 第二个参数是前导，主要是为了筛选。比如不要1到100000中不要连续数字62，此时你要要记录前导为6，然后你在当前dfs函数中变量时，判断i==2时，不符合要求。limit时一个上限制。
看题目：
dp[10][2]存储是否是前缀有6的数。
#include#include #include using namespace std;int dp[10][2],bit[10];int dfs(int len,bool if6,bool limit){ if(!len) return 1; if(!limit && dp[len][if6]!=-1) return dp[len][if6]; int res=0,up = limit ? bit[len] : 9; for(int i=0;i<=up;++i) { if(i==4 || if6&&i==2) continue; res += dfs(len-1,i==6,limit&&i==up); } //不是limit表示里面有0-9的数字 if(!limit) dp[len][if6] = res; return res;}int fun(int n){ int len = 0; while(n) { bit[++len] = n%10; n /= 10; } return dfs(len,false,true);}int main(){ memset(dp,-1,sizeof(dp)); int a,b; while(~scanf("%d%d",&a,&b),a&&b) { printf("%d\n",fun(b)-fun(a-1)); } return 0;}
#include#include #include #include using namespace std;long long dp[20][2],bit[20];long long dfs(int len,bool if4,bool limit){ if(!len) return 1; if(!limit && dp[len][if4]!=-1) return dp[len][if4]; long long res=0,up = limit ? bit[len] : 9; for(long long i=0;i<=up;++i) { if(if4 && i==9) continue; res += dfs(len-1,i==4,limit&&i==up); } if(!limit) dp[len][if4] = res; return res;}long long fun(long long n){ int len = 0; while(n) { bit[++len] = n%10; n /= 10; } return dfs(len,false,true);}int main(){ int t; scanf("%d",&t); memset(dp,-1,sizeof(dp)); while(t--) { long long n; scanf("%lld",&n); printf("%lld\n",n-(fun(n)-1)); } return 0;}
简单题
#include#include #include using namespace std;int bit[20];long long dp[20][10];long long dfs(int len,int pre,bool limit){ if(!len){ if(pre==0) return 1;return 0;} if(!limit && dp[len][pre] != -1) return dp[len][pre]; long long res = 0,up = limit ? bit[len] : 9; for(int i=0;i<=up;++i) { res += dfs(len-1,(pre+i)%10,limit && i==up); } if(!limit) dp[len][pre] = res; return res;}long long fun(long long n){ int len = 0; while(n) { bit[++len] = n%10; n /= 10; } return dfs(len,0,true);}int main(){ int T; scanf("%d",&T); for(int t=0;t
多维度数位DP
亦或
恨七不成妻