LeetCode #837 New 21 Game

LeetCode #837 New 21 Game

简单来说,就是在 [1, W] 的范围内抽牌,抽到的牌即为点数,记到自己的分数里,分数大于等于 K 时,抽牌结束。 求当抽牌结束时,分数小于等于 N 的概率。

其实读完题目,大部分人估计都是懵的,读到 W 和 K 的时候,都还跟得上,但这最后的 N 是个什么鬼?

其实,可以先忽略这个 N 和范围判定,它也只是最终所有可能结果中的一个而已。

看到一些题解,从结果的范围 [K, K + W) 来逆推,理解上稍微绕一些,这次试试从数学上模拟整个抽牌过程,复盘一下第 3 个例子:

1Input: N = 21, K = 17, W = 10
2Output: 0.73278

题目让我们求最终点数范围的概率,那我们干脆求出所有点数对应的概率,之后再对要求的范围做 sum 好了。

当第一次抽牌时,选项是 [1, 10],那么可能的结果,就是 1, 2, ..., 10,我们先来看看这几个数的概率。

怎么让点数是 1 呢?

只有第一次抽牌,就抽中 1 这一种可能了。

2 呢?

  1. 第一次抽牌,抽到了 2
  2. 先抽到了 1,然后再抽一张 1

3 呢?

  1. 第一次抽牌,抽到了 3
  2. 先抽到了 1,然后再抽到 2
  3. 先抽到了 2,然后再抽到 3

这就有点跳台阶的影子了。

为了达到分数 p:

因为在范围 [1, 10] 中,抽到每个点数都是等概率的 1/10,所以我们可以搞出这样一个状态转移方程:

1dp[i] = dp[i - 10] / 10 + dp[i - 9] / 10 + ... + dp[i - 1] / 10
2# 等效于
3dp[i] = 0.1 * sum(dp[i - 10 : i])

因为在点数大于等于 17 的时候,就不会再抽牌了,所以在计算点数为 18 的概率的时候,就没有从点数 17 再抽一张 1 这种可能了。

所以,我们先计算在 [1, 17) 范围内各点数的概率,因为一开始的点数是 0,即一定会经过总分数 0,同时也为了 index 处理方便,数组初始值就选 1 了:

1# 所有可能的分数为 [0, 26]
2dp = [1] * 27
3
4for i in range(1, 17):
5    # sum 范围是 i - 10,到 i - 1,max 处理越界
6    dp[i] = 0.1 * sum(dp[max(0, i - 10) : i])

那么在点数是 17 之后呢?每一个点数的前一个点数,最大只可能是 16 了,因为继续抽牌的前提是,游戏没有结束,所以:

1# 处理 [17, 26] 各种游戏结束时的可能值
2for i in range(17, 27):
3    # sum 范围是 i - 10,到 16
4    dp[i] = 0.1 * sum(dp[i - 10 : 17])

希望求出最后的值,在范围 [17, 21] 内的概率:

1# 0.7327777870686085
2return sum(dp[17 : 22])

把上面的逻辑整理一下,大概就有通用的解题思路了:

1def new21Game(self, N: int, K: int, W: int) -> float:
2    if K <= 0:
3        return 1
4    dp = [1] * (K + W)
5    for i in range(1, K):
6        dp[i] = 1 / W * sum(dp[max(0, i - W) : i])
7    for i in range(K, K + W):
8        dp[i] = 1 / W * sum(dp[max(0, i - W) : K])
9    return sum(dp[K : N + 1])

如果直接提交,肯定是会遇到超时的。

问题出在了哪儿呢?

分析下复杂度,在计算 [1, K + W) 的过程中,我们需要对之前的几个可能点数做 sum,如果第 i 项是对之前 10 个可能值做了 sum,那么 i + 1 项其实就没有必要再做一遍了。 如果不考虑边界,对于 i + 1 项的前一个点数来说,多了第 i 项,少了 i - 10 项,可以直接根据 diff 计算。

所以,来点优化:

 1class Solution:
 2    def new21Game(self, N: int, K: int, W: int) -> float:
 3        if K <= 0:
 4            return 1
 5
 6        dp, preSum = [1] * (K + W), 1
 7        for i in range(1, K):
 8            dp[i] = 1 / W * preSum
 9            preSum += dp[i]
10            if i >= W:
11                preSum -= dp[i - W]
12
13        for i in range(K, K + W):
14            dp[i] = 1 / W * preSum
15            if i >= W:
16                preSum -= dp[i - W]
17
18        return sum(dp[K : N + 1])

这下就没什么问题了,在所有的可能值 [1, K + W - 1] 中,每次的计算依赖前一次的结果,时间 O(n) 空间 O(n)。

但是真的没有优化可能了吗?

我们知道 N 代表游戏结束时的一个值,在 [K, K + W - 1] 范围内,所以对于上面的解法,在 N 之后的值,我们都是不需要的,可以节省 [N, K + W - 1] 范围的时间消耗,那么空间呢?同样,分配数组时,到 N 就足够了。

另一方面,两个由 K 划分的区间,也可以合并为一个。

最终优化结果:

 1class Solution:
 2    def new21Game(self, N: int, K: int, W: int) -> float:
 3        if K <= 0:
 4            return 1
 5
 6        dp, preSum = [1] * (N + 1), 1
 7        for i in range(1, N + 1):
 8            dp[i] = 1 / W * preSum
 9            if i < K:
10                preSum += dp[i]
11            if i >= W:
12                preSum -= dp[i - W]
13
14        return sum(dp[K : N + 1])