不了解dp的可以先看一下dp
数位dp含义：
数位：一个数有个位，十位，百位，千位等等，数的每一位都是数位。
数位dp归为计数dp，是在数位上进行操作的dp。
数位dp的实质是一种快速枚举的方式，它满足dp的性质，然后进行记忆化搜索。
用途：
有两个数，两个数范围很大(例如1e9，甚至更大)，求这两个数符合限定条件的个数。纯暴力不行，就要用数位dp。
例子：求从0到n,（n为2^32-1）,(条件)求包含49的数有多少；
思路or具体实现：
n为2^32-1，数位其实只有20位，枚举数位，就不会超时。
dp[shuwei][diaojian]。dp的第一维通常是数位，后面的几维根据题目条件来设定。上面给的例子只用了一维。
控制上界枚举，从最高位往下枚举。用记忆化搜索来做，抛开循环后转移状态能更加随意，大部分数位和动态规化的题都可随意切换。搜索与循环异曲同工之妙，但前者更易转移状态，在限制较多的情况下被大部分人喜爱。
例题:Bomb
思路 ：数位dp=dfs+记忆化搜索。
需要注意上限即题目所给范围的预处理，本题用digtis[20] 数组，存储上限的数位，最好用一个函数来处理，比如solve(sum),处理时，对上限的数位总数拿一个变量进行存储,比如k或len。
在dfs中用 limit (有些题解是top）判定上限，dfs(len,条件，limit)；
dfs执行数位dp，在搜索时用了 up_bound=(limit?digit[len]:9); 来标记上限，同时用cnt来存储满足的条件的数量，然后更新dp数组，更新时要满足if(!limit)，到达上界，状态不完整。
在dfs中对条件的处理，需要根据题意去确定，每个题目不一样。
是否顶着上界，每层确定这一位选啥，判断是否和上一位冲突，全部确定完了方案数+1。
由于顶着上界是比较特殊的情况，所以这类答案直接一层层搜索出答案，不用记忆化，其他(不顶着上界)的情况用dp[][] 直接返回数量。
有些题目需要最后算一下最高位为0的情况。
#include<bits/stdc++.h> using namespace std; typedef long long LL;int digit[20]; //储存上界的每个数位 LL dp[20][2]; //统计没有49的总数 //if4它的上一位和当前位是否是4 //len 记录当前数位，从高位往下搜索 //limit 上一位是否是上界 LL dfs(int len, bool if4, bool limit){if(len==0) return 1ll; //个位的时候，有一个分支。 if(!limit && dp[len][if4]) return dp[len][if4];//没到达上界并且数位已经统计过，直接返回数量。 LL cnt=0,up_bound=(limit?digit[len]:9);//标记数位的上界 //对整个数位进行记忆化搜索 for(int i=0;i<=up_bound;++i){if(if4&&i==9) continue;//碰到49不加入。cnt+=dfs( len-1, i==4,limit && i==up_bound);//向下搜索，判断上一位是否为4，上一位是否到达上界，当前位是否到上界。 } if(!limit) dp[len][if4]=cnt; //到达上界是状态不完整，不更新dp return cnt;//直接返回本次搜索结果，加入到最后结果中 }LL solve(LL num) //num是上界这个数 {int k=0;//记录数位个数。while(num){digit[++k]=num%10;num/=10; } return dfs(k,false,true); } int main(){int t;cin>>t;while(t--){LL n;cin>>n;cout<<n+1-solve(n)<<endl;} return 0; }
