数位DP

每天一道a+b系列新开一个专题，数位DP

数位DP，无法暴力求解，需要在数位上进行递推，一般都采用记忆化搜索的方式

常见题型为求区间【l，r】的某类符合条件的值，转为【0，r】-【0，l-1】来计算

一般需要用数位来预处理

数学上对数比大小的原则：

对于一个小于n的数，肯定是从高位到地位出现了某一位<n的那一位

（不要以为是废话，这是数位DP的代码原理）

如n=4567

要小于n的话，首先最多是四位数（有些题目允许前导0）

枚举千位：0，1，2，3，4（当然4是特殊情况）

枚举百位：如果千位选择的是0，1，2，3，那么不仅百位随便选，之后的都能随便选了；如果选择的是4，那么百位选择为0，1，2，3，4，5（当然5也是特殊的）

从上述举例看出，由于数字比大小的原则，我们可以从高位到低位枚举第一次<n的对应是哪一位

接下来是模板中的状态定义，直接影响对于数位dp的理解

定义dp【i】【st】：（可能允许前导0）位数为i，状态为st的方案数

这里的状态st指的是根据题目自己定义的状态

如st=0为合法状态，st=1为不合法状态。然后dp【i】【0】与dp【i-1】【1】、dp【i-1】【0】有数学上的转移关系

全靠自己对题的理解，定义状态和设计状态转移

根据上面的分析，写成记忆化搜索呢，需要三个参数

设定为：pos，status，flag

pos：从高位到低位依次枚举，现在枚举到的是第几位

status：自己定义的状态

dp【pos】【status】为需要记忆化搜索的值

flag：flag为bool型变量，为true表示从高位枚举到第len位，已经有某一位出现了小于n的对应位置了（意味着剩下的位可以随便选择）

同理，flag为false，表示从高位枚举到第len位，已经有某一位出现了小于n的对应位置了（意味着剩下的位可以随便选择）

然后，就是第len位的选择和dp【len】【status】的dp转移了

发现，似乎少了些什么？如何判断flag？

需要以n的每个位置的数的大小比较，所以呢，需要把n一位一位的分隔看

不妨定义为digit【i】是n的第i位的数值

拿n=4567举例，digit【1】=7，digit【2】=6，digit【3】=5，digit【4】=4，从高位到地位开始枚举计算

光说不练假把式，下面来刷题，用模板来做这些题，都很简单的

刷一波题，来一波题解链接

HDOJ3555：题解here

HDOJ2089：题解here

HDOJ4352_XHXJ's LIS：题解here

HDOJ3652_B number：题解here

HDOJ4389_X mod f(X)：题解here

URAL1057_Amount Of Degrees：题解here

BZOJ1026_windy数：题解here

HDOJ3709_Balanced Number：题解here

CF55D_Beautiful numbers：题解here

HDOJ4734_F(X)：题解here

HDOJ4507 恨7不成妻：题解here

POJ3252 Round Numbers：题解here

CF258B Little Elephant and Elections：题解here

HDOJ3271SNIBB：题解here

HDOJ3967Zero's Number：题解here

HDOJ3565 Bi-peak Number：题解here

HDOJ3943 K-th Nya Number：题解here

HDOJ5787 K-wolf Number：题解here