数位dp | fanz

数位 dp 适用于处理某一范围中所有数字的状态计算问题（比如计算中"1"出现的次数），这类问题如果使用暴力方式解决的话容易超时，使用数位 dp 可以更好的解决这个问题。

数位 dp 的思想其实就是从最高位向最低位（从前到后）枚举每一位数字，实际上，对于每一位数字，其实就是 0-9 这十个状态。可是如果对每一位都枚举 0-9，那么时间复杂度是，那么还是很容易超时；这个时候，如果搭配记忆化搜索，就能大幅降低时间复杂度，比如我们要计算中 1 的个数：

Info

从这个图中可以发现重复计算的部分和必须单独计算的部分。除第一位数字外，其余每位数字都可以取 0-9。
以第三位为例，如果第一位取 0，那么第二位无论取哪个数字，第三位都可以取 0-9；如果第一位取 1，那么第二位取 0-1 的时候，第三位也可以取 0~9，唯独达到最大值 2 的时候第三位才只能取 0~3。

那么，可以把每一位数字未达到最大值的状态保存下来，上面这个场景中，“可取 0~9”（即可取任意值）就是一个可重复计算的部分，"达最大值"是不可重复计算部分。因为可以发现，前几位未达到最大值时，后面几位均可以任意填，比如上面说的，第 1 位取 1，第二位取 0 和 1 时第三位都可以任选，这部分的计算就是重复的。

1. 数位 dp（仅上界）

仅上界的数位 dp 是最简单的写法，我们还是以计算中 1 的个数这个问题为切入点，逐步分析：

首先，将数字 123456 转换成数组 [1,2,3,4,5,6]，limit 为 true（表示是否达到最大值），prezero 为 true（表示是否有前缀 0;
从前到后逐位枚举，第 0 位是[1]，那么我们枚举 0 和 1；枚举 0 时，limit 为 false，之后每一位数字都可以取任意值，prezero 为 true；枚举 1 是，limit 为 true，下一位数字有上限限制，prezero 为 false，同时因为有 1，记录preones为 1；
进一步，针对上一步得到的(1,0,false,true)和(1,1,true,false)继续分析，如下图所示。

为什么需要 prezero？

如果不考虑 prezero，那么"00123"、"0123"和"123"会被认成三个数字，导致计算结果出错

可以发现，如果 limit 为 true，那么下一个数字会受到上限影响，此时结果不固定，不能提前存储；如果 prezero 为 true，那么可能导致重复计算。因此，当且仅当 limit 和 prezero 都为 false 的时候才能记忆化，因为之后的数字可取任意值，不受上限影响，也没有重复计算。

// 单上界写法
  private int digit_dp(boolean limit, boolean prezero, int index, int preones, int[] curval) {
    if (index == curval.length) {
      return preones;
    }
    if (!limit && !prezero && dp[index][preones] >= 0)
      return dp[index][preones];
    int high = limit ? curval[index] : 9;
    
    int res = 0;
    for (int i = 0; i <= high; i++) {
      res += digit_dp(limit && i == high, prezero && i == 0, index + 1, preones + i, curval);
    }
    if (!limit && !prezero) {
      dp[index][preones] = res;
    }
    return res;
  }

2. 数位dp（上下界）

仅上届写法比较好理解，搭配前缀和写法其实就已经能够解决[val1,val2]范围内的数字信息问题，但如果我们就是想一次解决此问题呢？其实也可以，不过为方便计算，建议将val1和val2预处理为长度一致的数组：

private int digit_2_dp(boolean limithigh, boolean limitlow, boolean prezero, int index, int preones, int[] lowval,
      int[] highval) {
    // 这里强制让low和high的长度变成一样的
    if (index == lowval.length) {
      return preones;
    }
    if (!limithigh && !limitlow && !prezero && dp[index][preones] >= 0)
      return dp[index][preones];
    int low = limitlow ? lowval[index] : 0;
    int high = limithigh ? highval[index] : 1;
    int res = 0;
    for (int i = low; i <= high; i++) {
      res += digit_2_dp(limithigh && (i == high), limitlow && (i == low), prezero && (i == 0), index + 1,
          preones + ((i == 1) ? 1 : 0), lowval, highval);
    }

    if (!limithigh && !limitlow && !prezero)
      dp[index][preones] = res;
    return res;
  }