0%

LeetCode 笔记之——837. 新 21 点

题目

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

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

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

1. 题解思路

问题要求的东西,是爱丽丝最后分数的概率;

而分数,在什么时候不会变动呢?就在不能抽牌的时候!

所以,爱丽丝停止抽牌的时机点在哪?

当分数不少于 K,即分数大于等于 K 时,爱丽丝就会停止抽牌,所以最后一次抽牌的时间点就在分数等于 K - 1 时!

所以从最后一个可抽牌时机,当且仅当分数为 K - 1 时进行分析!

2. 以 N = 21,K = 17,W = 10 为例

此时最后一个可抽牌分数为 16;

那么,当分数为 16 的时候,再抽一张牌,所得分数不大于 21 的概率,则有:

  1. 如果抽到 1,那么此时分数为 17,不能继续抽牌,显然此时 17 < 21,概率为 1
  2. 如果抽到 2,那么此时分数为 18,同理,概率为 1
    \cdots
  3. 如果抽到 5,那么此时分数为 21,同理,概率为 1
  4. 如果抽到 6,那么此时分数为 22,概率为 0
  5. 如果抽到 7,那么此时分数为 23,概率为 0
    \cdots
  6. 如果抽到 10,那么分数为 26,概率为 0

由于抽到每一张牌的概率是等可能的,因此,就有:

f(16)=110×[1+1+1+1+1+0+0+0+0+0]=0.5\begin{aligned} f(16) &= \frac{1}{10} \times [1 + 1 + 1 + 1 + 1 + 0 + 0 + 0 + 0 + 0]\\ \\ &= 0.5 \end{aligned}

那么对于 16 而言,其最终分数不大于 21 点的概率为 0.5

当分数为 15 时,爱丽丝再抽一张牌,其分数有可能变为 [16, 25],那么其最终分数不大于 21 点的概率则有:

f(15)=110×[f(16)+1+1+1+1+0+0+0+0+0]=0.5\begin{aligned} f(15) &= \frac{1}{10} \times [f(16) + 1 + 1 + 1 + 1 + 0 + 0 + 0 + 0 + 0]\\ \\ &= 0.5 \end{aligned}

从这里,我们可以看出规律:

f(x)=1W×[f(x+1)+f(x+2)++f(x+W)]f(x) = \frac{1}{W} \times [f(x + 1) + f(x + 2) + \cdots + f(x + W)]

其中 xx分数,而 f(x)f(x) 则为 当分数为 xx 时,最终分数不大于 NN 的概率

所以,f(0)f(0) 即为 当分数为 00 时,最终分数不大于 NN 的概率,就是我们要求的结果。

得出方程之后,很容易就可以看出,f(x)f(x) 的结果和其后面 W\mathrm{W} 个的结果相关;

所以,这就是一道 动态规划 题目!

3. 动态规划三板斧

3.1. 初始状态

K 之后的值就不变了,同时 f(x)f(x) 的结果和其后面 W\mathrm{W} 个的结果相关;

因此,我们只需要关心 K+WK + W 个值即可;

所以,初始化 K+WK + W 长度的数组,[K,K+W][K, K + W] 的值对应进行初始化即可

3.2 状态转移方程

从上面可以得到公式

3.3 终止状态

x=0x = 0 时,f(x)f(x) 即为所求

4. 优化与坑点

4.1 更好的状态转移方程

我们看到,对于 f(x)f(x) 而言,需要求解 W\mathrm{W} 长度的值才能得到;

如果 W\mathrm{W} 很大,就会导致超时。

观察 f(x)f(x) 的表达式可以看出,它与 f(x1)f(x - 1) 是错位的:

f(x)=1W×[f(x+1)+f(x+2)++f(x+W1)+f(x+W)]f(x1)=1W×[f(x)+f(x+1)++f(x+W1)]\begin{aligned} f(x) &= \frac{1}{W} \times [f(x + 1) + f(x + 2) + \cdots + f(x + W - 1) + f(x + W)] \\ f(x - 1) &= \frac{1}{W} \times [f(x) + f(x + 1) + \cdots + f(x + W - 1)] \\ \end{aligned}

因此,就可以采取 错位相减法,消除多余的项:

f(x1)f(x)=1W×[f(x)f(x+W)]f(x1)=1W×[f(x)f(x+W)]+f(x)\begin{aligned} &\therefore f(x - 1) - f(x) = \frac{1}{W} \times [f(x) - f(x + W)] \\ \\ &\therefore f(x - 1) = \frac{1}{W} \times [f(x) - f(x + W)] + f(x) \\ \end{aligned}

最终我们得到的方程

f(x)=1W×[f(x+1)f(x+W+1)]+f(x+1)f(x) = \frac{1}{W} \times [f(x + 1) - f(x + W + 1)] + f(x + 1)

这个方程只需要计算两项,大大减少了计算的数量。

4.2 N\mathrm{N}K+W\mathrm{K + W} 之间的关系

在构造初始状态的时候,我们可以得知,在 [K, N] 时,概率为 1;

[N, K + W - 1] 时,概率为 0;

我相信很多人的第一反应应该是这样;

但是这里我们就犯了一个先入为主的错误,认为 N\mathrm{N} 一定在 K\mathrm{K}K+W1\mathrm{K + W - 1} 之间,实际上一定是这样吗?

肯定不是!

例如 N=10000,K=17,W=10\mathrm{N = 10000, K = 17, W = 10} 时,N\mathrm{N} 就肯定不在 [K, K+W1][\mathrm{K}, \ \mathrm{K + W - 1}] 之间。

NK+W1\mathrm{N} \ge \mathrm{K + W - 1} 时,则对于 [K, K+W1]\mathrm{[K, \ K+W-1]} 中的所有概率都为 1\mathrm{1}

因此,在初始化时,我们的分界点应该是

N=min(N,K+W1)\mathrm{N^\star = \min(N, K + W - 1)}

4.3 对于 dp[K -1] 的简便求法

对于我们需要计算的第一个值,就是我们初始状态的 dp[K - 1],对于这个值,我们不能套用上面优化过后的公式;

因为这个公式是一个递推式,需要通过第一个值来计算得出,那么显然我们的第一个值就是 dp[K - 1]

dp[K - 1],从例子中,我们是通过其后面的 W\mathrm{W} 个值计算出来的;

那么这里就有问题了,当 W\mathrm{W} 很大的时候,我们求解 dp[K - 1] 就会耗时比较长。

其实经过观察,我们可以看出,对于 dp[K - 1] 有:

f(K1)=1W×[f(K)+f(K+1)++f(K+W1)]f(K1)=1Wi=KK+W1f(i)\begin{aligned} f(K - 1) &= \frac{1}{W} \times [f(K) + f(K + 1) + \cdots + f(K + W - 1)] \\ f(K - 1) &= \frac{1}{W} \cdot \sum_{i = K}^{K + W - 1}f(i) \end{aligned}

对于 f(i)f(i) 则有:

f(i)={1,KiN0,N<iK+W1N=min(N,K+W1)f(K1)=1Wi=KNf(i)f(K1)=1W(NK+1)\begin{aligned} f(i) &= \begin{cases} 1, & K \le i \le N^\star \\[2ex] 0, & N^\star \lt i \le K+W-1 \\ \end{cases} \\[5ex] N^\star &= \min(N, K + W - 1) \\[5ex] \therefore f(K - 1) &= \frac{1}{W} \cdot \sum_{i = K}^{N^\star}f(i) \\ f(K - 1) &= \frac{1}{W} \cdot (N^\star - K + 1) \\ \end{aligned}

最终,我们得到了

f(K1)=1W(NK+1)f(K - 1) = \frac{1}{W} \cdot (N^\star - K + 1)

可以在 O(1)\mathrm{O(1)} 时间复杂度就求解出 dp[K - 1]

4.4 特殊情况

到现在为止,我们还没有考虑一些特殊情况,如:

  1. N0N \le 0
  2. K0K \le 0
  3. W0W \le 0

从题目提示中,我们发现只有 K=0K = 0 是可能的,因为 NK0N \ge K \ge 0W1W \ge 1

所以当 K=0K = 0 的时候,玩家不能抽牌,所得分数一定不会大于 NN,所以此时概率为 11

5. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
fun new21Game(N: Int, K: Int, W: Int): Double {
// 0. K == 0 的特殊情况
if (K == 0) {
return 1.0
}

// 1. 初始化 K + W 个元素
val dp = DoubleArray(K + W)

// 2. dp[K..N*] = 1
val spanPoint = kotlin.math.min(N, K + W - 1)
for (i in K..spanPoint) {
dp[i] = 1.0
}

// 3. 计算 dp[K - 1]
dp[K - 1] = (1.0 / W) * (spanPoint - K + 1)

// 4. for K-2 until 0
((K - 2) downTo 0).forEach {
dp[it] = (1.0 / W) * (dp[it + 1] - dp[it + 1 + W]) + dp[it + 1]
}

// 5. 结果即为 dp[0]
return dp[0]
}
}