简介

数位DP是一种基于数位分解和动态规划的算法，用于解决与数字的每一位相关的计数问题。它通过将数字分解为每一位上的数字，然后逐位进行状态转移，从而高效地解决复杂的问题。

思想

  1. 数位分解：将一个数字分解为每一位上的数字。例如，数字 123 可以分解为 [1, 2, 3]。
  2. 状态定义：定义动态规划的状态，通常包括当前处理到的数位、是否受到上下界限制、是否包含某些特定数字等。
  3. 状态转移：通过逐位处理，从高位到低位递归地进行状态转移，计算满足条件的数字数量。
  4. 记忆化搜索：为了避免重复计算，使用记忆化搜索（一般情况下记忆化搜索写起来比递推方便）。

模板

注意当有上下界时，下界lower和上界upper数位个数如果不一致时，lower要补前导0（参见力扣1742）

代码以统计数字1的个数为例：

1
2
3
4
5
6
7
8
9
10
11
12
public int dfs(int idx, int cnt, boolean isLimit){
    int n = str.length();
    if(idx == n) return cnt;
    if(!isLimit && cache[idx][cnt] != -1) return cache[idx][cnt];
    int ret = 0;
    for(int i = 0; i <= 9;++i){
        if(isLimit && str.charAt(idx)-'0' < i) break;
        ret += dfs(idx+1, cnt+(i == 1 ? 1 : 0), isLimit && str.charAt(idx)-'0' == i);
    }
    cache[idx][cnt] = ret;
    return ret;
}

题目

__END__