数位dp总结 之 从入门到模板

基础篇 数位dp是一种计数用的dp，一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp，字面意思就是在数位上进行dp咯。数位还算是比较好听的名字，数位的含义：一个数有个位、十位、百位、千位......数的每一位就是数位啦！

之所以要引入数位的概念完全就是为了dp。数位dp的实质就是换一种暴力枚举的方式，使得新的枚举方式满足dp的性质，然后记忆化就可以了。

两种不同的枚举：对于一个求区间[le,ri]满足条件数的个数，最简单的暴力如下：

[cpp]  view plain  copy for(int i=le;i0) return 0;//最坏的情况，这一位及后面的全部为9都不能达到0那就直接GG，这个剪枝不会影响ac       if(pos==-1) return sum==0 && val==0;       if(dp[pos][sum][val][limit]!=-1) return dp[pos][sum][val][limit];       int up=limit?a[pos]:9;       ll ans=0;       for(int i=0;i