数位dp总结-蒲公英云

数位dp总结

数位dp的题目一般问的是某个区间内满足某种性质的数的个数，而且对于数位dp的题目一般有都有比较通用的做法，在考虑问题的时候一般以树的形式来考虑：

watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16

一般来说数位dp的迭代代码都长下面这样，只是不同的问题处理逻辑不太一样：

if __name__ == "__main__":
    n = 10
    B = 2
    nums = list()
    while n > 0:
        nums.append(n % B)
        n //= B
    # last记录前缀信息, 一般与题目中给定的信息有关
    res, last = 0, 0
    for i in range(len(nums) - 1, -1, -1):
        ...
        if ... : break

一般我们需要记住题目中涉及到的性质：① 包含K个1 ② 不降数 ③ 相邻两个数的差大于等于2 ④ 个数数字之和取模等于0 ⑤ 不包含4与连续的62；记住这些性质这样我们在遇到类似题目的时候可以反映出怎么样通过递推来预处理二维数组f。数位dp的难点在于预处理，因为预处理本身就是一个dp的过程，一般在考虑状态计算的时候都是枚举最高位和次高位填的数字来计算的。可以发现在状态计算的时候度的数量，数字游戏，数字游戏II和Windy数都是枚举最高位和次高位的数字填什么进行状态计算的。上面的都是数位dp的迭代写法，其实还有一种比较通用的做法是使用dfs来解决，数位dp的dfs写法有一个很大的优点是思维量与代码量都比较小，而且使用记忆化搜索也很快算出来，比较适合于求解比较复杂，涉及到性质比较多的数位dp题目。