LeetCode 新 21 点——DP、马尔科夫链和前缀和

0. 题干

LeetCode #837 新 21 点题干如下：

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：

爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。 每次抽取都是独立的，其结果具有相同的概率。

当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/new-21-game 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. 正向计算停机概率

拿到题目，首先想到的是计算停机概率—— $p\left( i \right)$ 定义为最终停机在和为 $i$ 的概率。显然，这里有 $$i \in \left[K, K-1+W \right]$$ 对于题目要求的 $p(sum \le N)$，显然为 $\sum_{i=K}^{N}p\left(i\right)$。因此，我们只需要计算出停机概率 $p(i)$，就可以解决这个问题。

1.1 暴力模拟

首先考虑对原始流程进行暴力模拟。令 $${p^m}\left( i \right)$$ 为第 $m$ 次抽卡后手上和为 $i$ 的概率，那么我们可以这样进行模拟（暂时不考虑边界条件）： $${p^{m + 1}}\left( i \right) = \sum\limits_{k = 1}^W {p\left( {i - k} \right){1 \over w}} \tag{1.1}$$ 显然，进行 $m$ 次抽卡后，全部可能的点数和都不小于 $m$，因此我们最多只需要进行 $k$ 次模拟，每次模拟需要计算最坏 $k+w$ 个可能点数和的概率，求和复杂度为 $w$。最后需要进行一个求和操作。因此，总体的算法复杂度为 $$O(k (k+w) w)$$

1.2 马尔科夫链优化

对这种问题，我们很容易发现式 $(1.1)$ 可以写成马尔科夫链的形式：

$${p^{m + 1}} = \left( \begin{matrix} {{p^{m + 1}}\left( 0 \right)} \cr {{p^{m + 1}}\left( 1 \right)} \cr \vdots \cr {{p^{m + 1}}\left( {k + w - 2} \right)} \cr {{p^{m + 1}}\left( {k + w - 1} \right)} \cr \end{matrix} \right) = \frac{1}{w} \left( \begin{matrix} 0 & {} & {} & {} & {} & {} & 0 \cr 1 & 0 & {} & {} & {} & {} & {} \cr \vdots & 1 & 0 & {} & {} & {} & {} \cr 1 & {} & \ddots & \ddots & {} & {} & {} \cr 0 & \ddots & {} & \ddots & 0 & {} & {} \cr \vdots & \ddots & \ddots & {} & 1 & 0 & {} \cr 0 & \cdots & 0 & 1 & \cdots & 1 & 0 \cr \end{matrix} \right) \left( \begin{matrix} {{p^m}\left( 0 \right)} \cr {{p^m}\left( 1 \right)} \cr \vdots \cr {{p^m}\left( {k + w - 2} \right)} \cr {{p^m}\left( {k + w - 1} \right)} \cr \end{matrix} \right) = \frac{1}{w} A{p^m} \tag{1.2}$$

转移矩阵 $A$ 有 $m$ 个下对角线元素全为 1。

而显然， $$p^0=\left(\begin{matrix} 1 & 0 & \cdots & 0 \cr \end{matrix} \right)^T$$ 因此，我们只需要求出 $A$ 的阶乘即可求出 $p^m$，进而求出结果。而这个矩阵的阶乘是比较好求的。简单分析可知， $A^m$ 的性质有：

• 其主对角线及以下 $m$ 行对角线都全为 0
• 其每行对角线都为相同值，因此可以用第一列表征全部状态。

由性质 2，定义 $a^m$ 为其第一列。有

$$a_i^{m+1} = \sum\limits_{ j=\max(1,i-w) }^{i-1} {a^m_j}$$

注意到上式为连续和，因此我们可以用前缀和（$O(n)$ 额外空间），或是使用滑动窗口（$O(1)$ 额外空间）来加速运算，将单次矩阵乘法运算优化到 $O(k+w)$。

这样，我们可以用 $O((k+w)k)$ 的复杂度得出最终结果。

1.3 考虑使用快速幂加速矩阵阶乘

看到 $A^m$ ，我们可以考虑使用快速幂加速矩阵运算。这样，我们需要进行 $O(\log m)$ 次矩阵乘法运算。每次乘法运算为 $A^m A^m$ 或 $A^l A^m$。考虑我们之前提到的性质，我们可以痛苦地发现每次运算都是 $O((k+w)^2)$ 的。这样通过尝试减少乘法运算次数，我们丢掉了矩阵 $A$ 友好的特征，成功地提高了每次乘法运算的复杂度，反而得到了更高的总复杂度。亏本的买卖还是别干了。

1.4 使用 dp 直接计算最终概率

上面通过马尔可夫链，我们计算的是一次次抽卡的概率。能不能跳过抽卡过程、直接计算最终的停机概率呢？是可以的。考虑这样的定义：

定义 $p(i)$ 为点数和在抽卡过程中经过了 $i$ 的概率。当 $i\ge K$，定义 $p(i)$ 为停在 $i$ 的概率。

同样不考虑边界条件下，我们有： $$p\left(i\right)=\sum_{j=1}^W{\frac{1}{W}p\left(i-j\right)} \tag{1.4}$$ 显然这是一个简单的 DP 问题。通过前缀和或是滑动窗口，我们可以将总体复杂度优化到 $O(k+W)$。

2. 反向直接计算获胜概率

前面我们通过正向计算出停机在 $i$ 点数和的概率。那么反过来，我们可以计算出，当前（某一次抽卡）点数和为 $i$ 时，最终获胜（最终停机点数和不超过 $N$ ）的概率。记为 $p(i)$。

对于停机的状态 $K \le i \le K-1+W$，我们可以直接写出 $p(i)$。对于未停机状态，有下面转移方程： $$p(i)=\frac{1}{W}\sum_{j=1}^{W}p(i+j)$$ 一顿 DP，计算出的初始状态概率 $p(0)$ 就是结果。

3. 总结

反向计算很直观，定义很简单，很容易理解。而正向计算需要证明公式 (1.4)，并不是特别直观，而且需要处理的边界条件其实还是比较烦的。但是正向计算不依赖于 $K$ 就可以计算出停机概率，通过正向过程中维护前缀和，最终可以 $O(1)$ 时间内求出任意 $K$ 的获胜概率。从这个角度来说，我比较喜欢正向计算。