数位dp模板

数位 DP 是一类动态规划算法，用于计算某个数的某种性质。通常情况下，数位 DP 需要将数分解成某种形式，然后逐位进行计算。下面是一个简单的数位 DP 模板：

def digit_dp(pos, sum, limit):
    if pos == -1:
        return sum
    if not limit and dp[pos][sum] != -1:
        return dp[pos][sum]
    up = 9 if limit else digit[pos]
    res = 0
    for i in range(up + 1):
        res += digit_dp(pos - 1, sum + i, limit and (i == up))
    if not limit:
        dp[pos][sum] = res
    return res

其中，`pos` 表示当前处理的位数，`sum` 表示当前已经处理的位数上的数的性质，`limit` 表示是否达到上界。在每一次递归中，我们枚举当前位数上可以取到的数，然后递归计算下一位的结果。在计算结果的过程中，需要根据 `limit` 的值来判断是否达到上界，以便得到正确的结果。另外，还需要记录已经计算过的状态，以便避免重复计算。