统计数字出现次数的数位动态规划解法-数位统计DP
在处理数字问题时，我们经常遇到需要统计一定范围内各个数字出现次数的情况。这类问题虽然看起来简单，但当数字范围较大时，直接遍历统计的方法就变得不再高效。本文将介绍一种利用数位动态规划（DP）的方法来解决这一问题，具体来说，是统计两个整数a和b之间（包含a和b）所有数字中0到9每个数字出现的次数。
原题链接：338. 计数问题 - AcWing题库
数位动态规划概述
数位DP是一种用于解决与数字的各个数位相关的问题的动态规划技术。它通常涉及到将问题分解为更小的、更易于管理的子问题，然后使用递归或迭代来解决这些子问题，同时避免重复计算。
数位DP问题的关键在于如何定义状态和状态转移方程。在数位统计问题中，一个常见的状态定义包括：
-
当前处理的数位位置（从最低位到最高位）
-
当前数位的取值范围是否受到限制（即是否需要与给定的上限数值相匹配）
-
其他可能影响问题解的额外条件，如前导零的处理、特定数位的取值等
状态转移则依赖于当前处理的数位以及之前数位的选择如何影响后续数位的选择。
问题描述
解题思路
这个问题的关键在于如何有效地对每个数字位上0至9的出现次数进行统计。我们可以通过枚举每个数字0至9在不同的数位上的出现情况来进行分类讨论。
数位拆分
首先，我们需要将给定的数字拆分成单个数位，便于后续的处理。这可以通过不断取余和除以10来实现。
分类讨论
当我们考虑一个数字，比如说abcdefg，在这个数字中，我们关注的是2出现在第4位的所有情况，即形如abc2efg。在这种情况下，我们需要考虑的是2之前的数位（abc）和2之后的数位（efg）。
对于2之前的数位（abc）来说，我们有两种情况需要考虑：