LC 6957. 统计范围内的步进数字数目

https://leetcode.cn/problems/count-stepping-numbers-in-range/

6月份有道数位dp的题目，当时看了有点似懂非懂的，今天正好试试，看看自己能不能做出来。

其中 `F(s)` 是计算小于等于s的，并且满足条件的数的个数。

i 表示寻找第几位
last 表示上一位选择的数字，可以是0. 但是需要判断这个0是不是第一个，由 `isFirst` 来判断
isLimit 表示之前选择的数字，已经确保可以小于s了。如果已经确保的话，那么在选择上空间不同。
isFirst 表示目前选择是不是第一个数字。

def F(s):
    @functools.cache
    def search(i, last, isLimit, isFirst):
        if i == len(s):
            return 0 if isFirst else 1

        ans = 0
        h = int(s[i])
        if isFirst:
            h2 = 9 if isLimit else h
            for d in range(0, h2 + 1):
                ans += search(i + 1, d, isLimit or d < h, d == 0)
        else:
            for d in (last - 1, last + 1):
                if d < 0 or d > 9 or (not isLimit and d > h): continue
                ans += search(i + 1, d, isLimit or d < h, False)
        return ans

    return search(0, 0, False, True)


def check(s):
    for i in range(1, len(s)):
        d = ord(s[i]) - ord(s[i - 1])
        if not (d == 1 or d == -1):
            return False
    return True


class Solution:
    def countSteppingNumbers(self, low: str, high: str) -> int:
        MOD = 10 ** 9 + 7
        h = F(high)
        l = F(low)
        ans = h - l
        if check(low):
            ans += 1
        return ans % MOD