数位DP
经典的数位Dp是要求统计符合限制的数字的个数。
一般的形式是：求区间[n,m]满足限制f(1)、f(2)、f(3)等等的数字的数量是多少。条件 f(i)一般与数的大小无关，而与数的组成有关。
善用不同进制来处理，一般问题都是10进制和二进制的数位dp。
数位dp的部分一般都是很套路的，但是有些题目在数位dp外面套了一个华丽的外衣，有时我们难以看出来。
例题：windy数
精华都在代码的注释里呢，好好看吧
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll l,r; int num[20]; ll f[20][20];/*按照题目定维数*/ ll dfs(int i,int last,bool have,bool lim) /*需要传递的各种参数，视题目而定*/ /*本题中分别表示当前到了第几位，上一位是什么， 有没有前导0，有没有顶上界*/ /*一般需要有的是位数，上界，其他视情况而定*/ { if(i==0) return 1;/*判断是否已经枚举完，返回1就表示你枚举的数是合法的*/ if(!have&&!lim&&f[i][last]!=-1)/*判断边界条件以及是否已经搜索过*/ return f[i][last]; int up=0;/*这一位枚举的上界*/ if(lim==1) up=num[i];/*上一位顶到上界的话对这一位就有限制*/ else up=9;/*如果上一位没有顶到上界的话这一位就可以随意*/ ll ans=0; int op=0;/*表示这一位选择的数是什么*/ for(int j=0;j<=up;j++) { if(abs(j-last)<2) continue;/*判断不合法条件*/ op=j; if(have&&j==0) op=-2; ans+=dfs(i-1,op,op==-2,lim&&j==up);/*继续记搜，一定要注意各种限制条件的传递*/ } if(!have&&!lim) f[i][last]=ans;/*在一定条件下记录记搜的答案*/ return ans; } ll work(ll x) { memset(num,0,sizeof(num)); int tot=0; while(x)/*把数字的各个位拆到数组中存储*/ { num[++tot]=x%10; x/=10; } memset(f,-1,sizeof(f)); return dfs(tot,-2,1,1); } int main() { scanf("%lld%lld",&l,&r); printf("%lld",work(r)-work(l-1));/*前缀和思想*/ }
关于数位dp的经验
1：注意很多时候带进去是n==0要特殊处理。
2：还有一般问[m,n]，我们求[1,n]-[1,m-1]但是有的时候m为0就炸了。
3：求所有包含49的数，其实就是（总数-所有不包含49的数）。前者的化需要有两维限制，一个是上一位是什么，一个是之前有没有49。但是后 者只需要记一个上一位是什么。就能好写一些。
4：一般问题的数位dp部分，都是套路，但是这并不代表它外面“华丽的外衣”和与其他算法结合的的部分也是无脑的。要看出它是考数位dp，要看出问题怎么变化一下就是数位dp了。
5：dp初始化memset要置为-1。不能置为0！！！！！！因为有很多时候dp值就应该是0，然后我们如果误以为是因为之前没有计算，重新计算的话，就会tle。
6：既然是记忆化搜索，那就可以剪枝！！！！可行性剪枝！！
7：注意windy数的情况，有时前导0也需要记的！！！
原文：https://www.cnblogs.com/lcezych/p/11454417.html