咕咕咕
0%

DP（五）

发表于 更新于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

数位 DP

数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 $0,..,9$，其他进制可类比十进制。

引入：

例 1：

求 $[a,b]$ 之间有多少个数满足：从高位到低位，各位上的数非递减。

对于数位 DP，普遍是利用差分，用 $[1,b]$ 的答案减去 $[1,a-1]$ 的答案得到 $[a,b]$ 的答案。

先来考虑一个大数比较的策略：

对于两个大整数 $a,b(a,b\leq 10^{10^6})$ 比较大小。

先比较 $a,b$ 的长度：

  • $lena>lenb$，$a>b$。
  • $lena<lenb$，$a<b$。

对于 $lena=lenb$ 的情况，继续讨论。从最高位开始，找到第一个 $a[i]\neq b[i]$：

  • $a[i]>b[i]$，$a>b$。
  • $a[i]<b[i]$，$a<b$。

若没有 $a[i]\neq b[i]$ 的位置，则 $a=b$。

这个过程启发，只要第一个不等的位置满足大小关系，那么后面的数位就可以取任意值。

所以对于例 $1$，可以枚举前缀相同的数位个数（前缀长度确定后数位固定）后枚举考虑那个满足小于关系的数位，对于后面的数位则可以取 $[0,9]$ 的任意数字。

状态：

设 dp$[x][y][0/1]$ 表示从高到低第 $x$ 位，第 $x$ 位为 $y$ 且最高位到第 $x$ 位是/不是前缀的合法数量。

转移：

$(x,a[x],0)\leftarrow(x-1,a[x-1],0)$ $a[x]\geq a[x-1]$

$(x,y,1)\leftarrow(x-1,a[x-1],0),…(x-1,1,1),(x-1,0,1)$ 且数位不递减

DP 式子：

1
2
3
4
5
6
7
8
9
10
For(i,1,n){
    For(j,0,9) dp[i][j][0]=dp[i][j][1]=0;
    For(j,0,9){
        if(j==a[i]-'0'&&a[i]>=a[i-1]) dp[i][j][0]=dp[i-1][a[i-1]-'0'][0];
        For(k,0,j){
            dp[i][j][1]+=dp[i-1][k][1];
            if(j<a[i]-'0') dp[i][j][1]+=dp[i-1][k][0];
        }
    }
}

最后的答案为 dp$[lena][a[lena]][0]+…+$dp$[lena][0][1]$。

时间复杂度：$O(c\log^2_ca)$。

空间复杂度：$O(c\log_ca)$。

$c$ 表示进制数。

空间易得滚动数组优化。

addition：

在上文中，“第一个不等关系的数位后可以取任意数字”。在这里注意到可以将后面视作一个子结构，因为“任意”说明此时的后续状态并不关心前半部分的内容。

而在之前的内容中，学习过“记忆化搜索”。若将这个“子结构”用递归的方式处理并记忆化，同样可以实现 DP 的过程。并且笔者看来相较扫表更容易理解。

新 DP 式子：

1
2
3
4
5
6
7
8
9
10
11
12
int dp(int x,int y,int z){
    int i,res=0;
    if(x==n) return 1;
    if(vis[x][y][z]) return mem[x][y][z];
    For(i,y,9){
        if(z==0&&i>a[x+1]-'0') break;
        if(z==0&&i==a[x+1]-'0') res+=dp(x+1,i,0);
        else res+=dp(x+1,i,1); 
    }
    vis[x][y][z]=1;
    return mem[x][y][z]=res;
}

对比两种实现方式：

扫表和记忆化搜索。

其实可以发现，扫表记录是从起点到当前状态的结果，记忆化搜索记录的是当前状态到终点的结果。

若目标问题更容易解决的是到终点的结果（或是更容易视作子结构）那么更适合记忆化搜索实现。反之，若是更容易解决到起点的结果，那么更适合扫表方式解决。

同时，容易发现，记忆化搜索无法进行滚动数组优化，因为它需要反复访问不同状态记录的结果，而不是像扫表仅依附于上一轮的值。

对应的，记忆化也并非毫无优势。记忆化搜索确保了状态都是有用的，不会访问到一些无用状态，而扫表是通过循环枚举，会覆盖整个 DP 数组空间。

总结：

数位 DP 整体是比较套路化的一种 DP，整体框架确定：

  • 枚举前缀，标记是否前缀
  • 枚举数位
  • 根据题目要求修改转移的状态

当然，难的题目也可以比较困难，而难的核心往往就是“根据题目要求修改转移的状态”，这需要结合实际题目考虑，但普遍较“套路”。