算法-动态规划(九)

概述

本文主要介绍数位 DP，与其相关的题目有：度的数量、数字游戏。

数位 DP 是在数位之上执行 DP，其实现往往有模板可循，我们在此列举并说明其模板：

// 数位DP通常需要求取指定区间[a,b]内满足条件的树的个数，为此我们可以求取[0,b] - [0,a-1]。

// 状态表示：第i位为j时，满足条件的数的个数。
int[][] f;
// 基于某进制保存各位上的数。
int[] nums;

// 从高到底遍历各位。
for (int i = nums.length - 1; i >= 0; i--) {
    // 获取当前位
    int num = nums[i];
    
    // 当前位取0~num-1时，统计个数。
    
    // 当前位取num时，记录相关信息
    
    // 当i=0时，循环即将结束，可能需要做一些边界处理。
}

数位 DP 其实就数位统计，只不过有些统计需要用到 DP 而已。

度的数量

题目描述及示例

求给定区间 $[X,Y]$ 中满足下列条件的整数个数：这个数恰好等于 $K$ 个互不相等的 $B$ 的整数次幂之和。

例如，设 $X=15,Y=20,K=2,B=2$，则有且仅有下列三个数满足题意：$17=2^4+2^0$$、18=2^4+2^1$、$20=2^4+2^2$。

Input:
// 第一行包含两个整数，分别表示X、Y。
15 20
// 第二行包含两个整数，分别表示K、B。
2 2
    
Output:
// 输出一个整数，表示满足条件的整数个数。

解题思路

• 数据存储

  numX[i] 用于存储 $B$ 进制表示的 $X$，numY[i] 用于表示 $B$ 进制表示的 $Y$。

• 状态表示

  根据题意，如果一个数满足条件，则其 $B$ 进制表示中 $K$ 位为 $1$，其余位均为 $0$。我们在此先行给出状态表示 $f[i][j]$：组合数 $C_i^j$ ，具体原因后续将会看到。

• 状态转移

  按照最上面所述的解题模板，我们应当从最高位第 $i$ 位进行枚举。假定需要求取指定区间 $[0,X]$ 内满足条件的数的个数、此时最高位为 $numX[i]$，如果 $numX[i] > 1$，则其有两种选择：其一，当前位取 $1$，后续 $i$ 位任取 $k - 1$ 个 $1$，如此组合得到的数一定满足条件，其个数为 $C_i^{k - 1}$ (这就是我们的状态表示)；其二，当前位取 $0$，后续 $i$ 位任取 $k$ 个 $1$，如此组合得到的数也一定满足条件，其个数为 $C_i^k$；如果 $numX[i] = 1$，则其同样有两种选择：其一，当前位取 $0$，后续 $i$ 位任取 $k$ 个 $1$，如此组合得到的数也一定满足条件，其个数为 $C_i^k$；其二，当前位取 $1$，此时后续 $i$ 位无法任意取 $i - 1$ 个 $1$，因为任取得到的数可能大于 $X$，此时就需要枚举第 $i - 1$ 位，根据其情况再做判断；如果 $numX[i] = 0$，则直接枚举第 $i - 1$ 位即可。

  如果 $numX[i] > 1$，统计两种选择所满足的数的个数后就可以直接退出循环了。如果按照解题模板那样，当前位取 $numX[i]$ 所得到的数都是不满足条件的。

  如果 $numX[i] = 1$，当前位取 $1$ 并开始枚举第 $i - 1$ 位时，需要统计当前位前方已有多少个 $1$。

  当枚举到第 $0$ 位时，如果当前位为 $0$ 且当前位前方已有 $K$ 个 $1$，则这也是一个满足条件的数。

  我们在此介绍简单说明 $f[i][j]$ 的状态转移方程 (就是组合公式 $C_i^k = C_{i - 1}^k + C_{i - 1}^{k - 1}$)：

  $$f[i][j] = f[i - 1][j - 1] + f[i - 1][j]$$

• 状态初始化

  我们只需置 $f[i][0] = 1,(i \leq 0 < f.length)$ 即可。

数字游戏

题目描述及示例

科协里最近很流行数字游戏。某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 $123,446$。现在大家决定玩一个游戏，指定一个整数闭区间 $[a,b]$，问这个区间内有多少个不降数。

Input:
// 输入两个整数，分别表示a,b。
1 19
    
Output:
// 输出一个整数，表示满足条件的数的个数。
18

解题思路

• 数据存储

  numA[i] 用于存储十进制表示的 $a$，numB[i] 用于存储十进制表示的 $b$ (假定数组高位对应数字的高位)。

• 状态表示

  我们可以这样表示状态 $f[i][j]$：第 $i$ 位放置 $j$、其余位随意放置时，满足条件的数的个数。

• 状态转移

  这道题与上题类似，假定需要求取指定区间 $[0,A]$ 内满足条件的数的个数，且最高有效位为第 $i$ 位、最高位数字为 $numA[i]$。当前位置取 $0 \sim (numA[i] - 1)$ 时，其余位可任取，故而我们统计 $\sum_{j = 0}^{numA[i]}(f[i][j])$ 以得到满足条件的数的个数；当前位置取 $numA[i]$ 时，其余位不可任取 (原因同上)，故而需要枚举第 $i - 1$ 位以根据其情况再做判断。

  当枚举第 $i - 1$ 位时，因为需要满足不降数条件，其取值需要小于等于 $numA[i]$，。

  对于状态 $f[i][j]$ 而言，它应当由状态 $f[i - 1][k],(k \leq j)$ 转移得到。其状态转移方程具体如下：

  $$f[i][j] = \sum_{k = 0}^j(f[i - 1][k])$$

• 状态初始化

  根据状态表示，我们如此初始化：指定 $f[0][j] = j,(0 \leq j < 10)$。