对数位dp的理解

我开始做数位dp相关习题的最主要原因就是被7.30阿里笔试第一题虐到了…当时答完题直接自闭，第一题都没做出来，然后上牛客看一个的解法说是数位dp，之后一查居然是算法竞赛才会研究的专题orz…不管怎么说最近的一段研究也算是让我摆脱了“大区间内满足条件的数字个数查找”类型的题目无从下手的尴尬处境，接下来就谈谈我对这类题目以及数位dp的看法

什么是数位dp

简单来说是对给定的一个相对大的数n，将n的从高到低位用一个数组保存，然后通过分析n的各个数位之间的依赖关系（通常是题目的约束条件，比如相邻两个数字之差啥的）进行动态规划的一个过程（这里用记忆化dfs实现比较好理解）

数位dp可以用来解决大区间内满足条件的数的个数查找类问题，让我们通过以下题目来对数位dp进行一个感性的认知：

leetcode 233 数字1的个数
给定一个整数n，计算所有小于等于n的非负整数中数字1出现的个数，其中1<=n<=10^8

leetcode 1067 范围内的数字计数
给定一个在 0到 9 之间的整数 d，和两个正整数 low 和 high 分别作为上下界。返回 d在 low 和 high 之间的整数中出现的次数，包括边界 low 和 high

leetcode 600 不含连续1的非负整数个数
给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1的个数。

leetcode 902 最大为N的数字组合
我们有一组排序的数字 D，它是  {'1','2','3','4','5','6','7','8','9'} 的非空子集。（请注意，‘0’ 不包括在内。）
现在，我们用这些数字进行组合写数字，想用多少次就用多少次。例如 D = {'1','3','5'}，我们可以写出像 '13', '551', '1351315' 这样的数字。
返回可以用 D 中的数字写出的小于或等于 N 的正整数的数目

代码模版以及分析过程

我会结合代码模版来对数位dp问题进行一轮分析
python代码模版如下（以leetcode 233为例）：

class Solution:
    def __init__(self):
        # 初始化n的上界数组a
        # 初始化记忆化数组dp，通常dp的大小需要通过分析题目来得出
        self.a = [0 for _ in range(12)]
        self.dp = [[-1 for _ in range(12)] for _ in range(12)] 

    def dfs(self, pos:int, pre:int, limit:bool)->int:
        if pos == -1:return pre
        if not limit and self.dp[pos][pre]!=-1:return self.dp[pos][pre]
        up = 9 if not limit else self.a[pos]
        ans = 0
        for i in range(up+1):
            if i==1:
                ans += self.dfs(pos-1,pre+1,limit and i==self.a[pos])
            else:
                ans += self.dfs(pos-1,pre,limit and i==self.a[pos])
        if not limit:self.dp[pos][pre] = ans
        return ans
    
    def solve(self,n):
        # 将输入的n的各个位保存在数组a中，称为n的上界数组，pos从高位开始依此向低位遍历
        pos = 0
        while n>0:
            self.a[pos] = n%10
            n //= 10
            pos += 1
        return self.dfs(pos-1,0,True)

    def countDigitOne(self, n: int) -> int:
        return self.solve(n)

其中dfs()函数用来进行记忆化递归，solve()对给定的上界n计算结果

dfs函数的设计

一般dfs()函数会保存以下几个状态变量：pos表示当前遍历的数位，limit表示当前位的上一位是否是一个上界数，zero（该题中不需要）表示当前位的上一位是否是前导0.
其中记忆化dp数组保存的是一般性的状态，即“当前位”的上一位既不是上界数也不是前导0的前提下，当前位满足题意的状态，需要在代码中用

if not limit and not zero and dp[pos]!=-1:return dp[pos]

来表示如果是一般性的状态，就直接返回记忆化数组中的值
如果某一位的上一位不是上界数组中的值，说明该位枚举任意数字都会使得当前的数超过上界n，这很好理解，比如我们有上界数为644，pos=1即当前处于枚举状态的位为十位，假设百位为5，那么pos位即可以枚举0-9之间的任意数字，都不会使得当前的数字超过644，反之如果pos的上一位（百位）为6，则pos位的枚举范围就被限定在了0-a[pos]内。盘清了该逻辑，就不难理解为什么要用记忆化数组保存一般性的状态了，因为一般性的状态会涉及到大量的重复计算

前导0的影响

假设上界n有x位，那么当我们枚举x-1至0位的时候会出现前导0，假设上界n为644，则当枚举0-99之间的数时会出现001,099之类的现象，此时需要根据题目来分析是否需要处理前导0现象