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 呢?
- 第一次抽牌,抽到了 2
- 先抽到了 1,然后再抽一张 1
3 呢?
- 第一次抽牌,抽到了 3
- 先抽到了 1,然后再抽到 2
- 先抽到了 2,然后再抽到 3
这就有点跳台阶的影子了。
为了达到分数 p:
- 在
p - 1
分的时候,再抽一张 1 - 在
p - 2
分的时候,再抽一张 2 - …
- 在
p - 10
分的时候,再抽一张 10
因为在范围 [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])