Leetcode Link: 233. 数字 1 的个数 - 力扣（LeetCode） 面试题 17.06. 2出现的次数 - 力扣（LeetCode）
题目
数位 dp
数位 dp 解决的是在某一个范围[L, R]上满足某种条件的数字的个数，一般 R 或者 L 或者范围都非常大，直接使用暴力枚举一定超时。
而数位 dp 则是将数字视为对应的字符串，通过逐位放置合法的数字来不断求解答案。从暴力枚举的思路上看，数位 DP 属于从左到右的尝试模型，但是要有更多，更复杂的状态，这要根据题目具体分析。
常见的状态是is_bound和is_zero
举例 想知道小于 3135 的数字的中，有多少数字的相邻位数大于等于2。
我们从左到右放置，假设放置到了第 2 位：
- 如果放置形如 13_ _，此时可以放置的数字范围是[0, 9]
- 如果放置形如 31_ _，此时允许的范围是[0, 3] 显然，我们需要有一个布尔变量指示当前位能够放置的数字的最大值。当前面位置的数字都是贴着放的时候，当前只能放置[0, num[i]]，反之，能放置[0, 9]
有时，前导 0 也会影响我们的某些判定，本例子中，如果前面都是前导0，则当前位是首位，是可以放置1的。因此，需要使用is_zero来指示我们前面是否已经不包含前导0了。
解法一
思路： 本题即采用数位 dp 的思路。
查找记忆的时候需要注意，当 is_bound=True 的时候，我们的 maxi 的范围是收到 num[i] 决定的，即是特殊的，因此不能再 memo 里面去直接取。
题解：
class Solution:
def countDigitOne(self, n: int) -> int:
s = str(n) # 先转换成字符串
memo = {} # 记忆化搜索
def process(i: int, cnt: int, is_bound: bool):
'''
i: 当前遍历的位置
cnt: 之前的所有位置上含有数字1的个数
is_bound: 是否贴着上边界放置数字
'''
# base case: 当遍历到越界，则返回之前所有含有的1的个数
if i == len(s):
return cnt
# 只有当不是贴边放的时候，才能尝试直接取
if not is_bound and (i, cnt) in memo.keys():
return memo[(i, cnt)]
maxi = int(s[i]) if is_bound else 9
res = 0
for val in range(maxi+1):
next_cnt = cnt+1 if val == 1 else cnt
res += process(i+1, next_cnt, is_bound and val==maxi)
if not is_bound: memo[(i, cnt)] = res
return res
return process(0, 0, True)启发和联系
本题不需要 is_zero，前导 0 的判定对放置没有影响。
由于里面设计到不好int到str和str到int的转换，尽量明晰哪个位置需要进行转换，不要乱了。