LeetCode-837-新21点-Python

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/new-21-game

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

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

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

示例 1：

 输入：N = 10, K = 1, W = 10
输出：1.00000
说明：爱丽丝得到一张卡，然后停止。

示例 2：

 输入：N = 6, K = 1, W = 10
输出：0.60000
说明：爱丽丝得到一张卡，然后停止。在 W = 10 的 6 种可能下，她的得分不超过 N = 6 分。

示例 3：

 输入：N = 21, K = 17, W = 10
输出：0.73278

提示：

0 <= K <= N <= 10000
1 <= W <= 10000
如果答案与正确答案的误差不超过 10^-5，则该答案将被视为正确答案通过。
此问题的判断限制时间已经减少。

思路：动态规划

题目中，提供了三个变量。N，K，W，这里先简单解释下三者分别是什么？

N：这里相当于一个界限，题目中要求的就是最终抽取数字和与 N 的比较判定输赢
K：这里表示一个可继续抽取数字的条件
W：数字面值，也就是抽取的数字，是在 1 ~ W 的范围内

现在先看示例 1：

N = 10, K = 1, W = 10

因为爱丽丝是以 0 开局的，此时 0 < K = 1，那么她现在可以继续抽数字，而数字面值范围在 [1, 10]。要求抽取数字和小于 N（N=10）的概率？这里能比较明显的看出来，概率是 1。因为面值在 [1, 10]，无论抽取那个数字，都会大于 K，符合不在抽取的条件，而且最终的和也会落在 [1, 10] 之间，这里的结果肯定小于等于 N。所以概率是 1。

再看示例 2：

N = 6, K = 1, W = 10

这里改动的是 N 值。抽取的情形也如示例 1，在面值 [1, 10] 的范围内抽取数字，无论抽到是哪个数字都不能再次抽取，因为和大于 K，最终的和同样落在 [1, 10] 之间。但是这里的 N 值已经变为 6，这里抽取最终数字和只有落在 [1, 6] 这部分才符合不超过 N，这部分占总体部分 60%，所以概率为 0.6。

而示例 3，则比较复杂。也是我们主要需要分析的一种情况。

我们可以看到，前面例子 1，2 中，爱丽丝以 0 开始抽取数字，之后与抽取的数字进行累加，然后跟 K 跟 W 比较，去确定是否可再次抽取，以及是否不超过 N？

其实这里可以看到，爱丽丝能够赢的概率其实是跟下一轮开始前的分数有关的。

现在令 dp[i] 表示从分数为 i 的情况下开始进行抽取数字能够赢的概率，那么最终要求的就是 dp[0] 的结果。

现在要求出状态转移方程，先看题目中所给的一些条件。

当分数超过 K 时，这个时候停止抽数字进行结算，当分数不超过 N 时则判定为胜利，否则失败。

现在，先看下最后一次能够抽取的最大分数。因为超过 K，不能够进行再次抽取。那么想要再次进行抽取，此时允许的最大分数即是 K – 1。那么再次抽取中可抽取最大的数字是 W，所以最大分数即是 K – 1 + W。

也就是说当 $K \leq i \leq min(N, K+W-1)$ 时，这个时候 dp[i]=1，而 $i > min(N,K+W-1)$ 时，dp[i]=0。

那么现在要求当 $0\leq i < K$ 时 dp[i] 的值，应该如何求？

其实当 $0\leq i < K$ 时，再进行抽取的时候，此时的概率是由后面抽取数字后累计分数是否超过 N 的概率总和。而前面题目说了，在 [1, W] 数字之间进行抽取的概率是相等的。那么状态转移方程则如下：

$$
dp[i] = \frac{dp[i+1]+dp[i+2]+…+dp[i+W]}{W}
$$

虽然状态转移方程已经求出来了，但是会发现将转移方程代入代码中会超时。下面进行优化：

在这里，我们先看 dp[i+1] 是怎样的？根据前面的状态转移方程：

$$
dp[i+1] = \frac{dp[i+2]+dp[i+3]+…+dp[i+W+1]}{W}
$$

不过这个时候 $0 \leq i < K-1$。

可以看到，其实 dp[i] 跟 dp[i+1] 中间有一大部分是相同的，那么 dp[i] 的值，可由 dp[i+1] 得到：

$$
dp[i]-dp[i+1] =\frac{dp[i+1]-dp[i+W+1]}{W}
$$

此时：

$$
dp[i] = dp[i+1] – \frac{dp[i+W+1]- dp[i+1]}{W}
$$

在这里，$i = K – 1$，不适用于上面的公式，那么将其代入最开始的转移方程中：

$$
dp[K-1] = \frac{dp[K]+dp[K+1]+dp[K+W-1]}{W}
$$

我们前面有个 $dp[i]=1$ 的条件，即是当 i 的取值范围在 $[K, min(N, K+W-1)]$。

此时，i 为 K-1 时再次抽取数字有可能赢的部分就落在 $min(N, K+W-1) – K + 1$ 次抽取数字上，那么结果为：

$$
dp[K-1]=\frac{min(N, K+W-1)-K+1}{W}=\frac{min(N-K+1, W)}{W}
$$

而其他的值则有新的转移方程进行求得。

具体的代码如下。

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        dp = [0.0] * (K+W)
        # 先对概率为 1.0 的情况进行处理
        # 就是 i 落在 [K, min(N, K+W-1)] 这部分
        for i in range(K, min(N, K+W-1) + 1):
            dp[i] = 1.0
        
        # 这里先计算 K - 1 的情况
        # 将推导的结果公式放在这里
        dp[K-1] = float(min(N-K+1, W) / W)
        # 这里开始从 K-2 计算到 dp[0] 的值
        for i in range(K-2, -1, -1):
            dp[i] = dp[i+1] - (dp[i+W+1]-dp[i+1]) / W
        
        return dp[0]

题目中使用的思路是动态规划，这里主要的难点在于推导状态转移方程。
根据题意，推导的方向是由后面的情况往前进行推导。先处理最后一次抽取数字的情况，然后再往类推。
游戏是否能赢，跟下一次开始抽取前的分数是关联的。当前抽取能赢的概率其实是由后面抽取数字后累计分数是否超过 N 的概率总和。根据这个就能够求得状态转移方程。
因为最初的转移方程会超时，那么将其进行优化。根据相邻差分，简化状态转移方程。

如果觉得文章写得还可以，欢迎关注。公众号《书所集录》同步更新，同样欢迎关注。

LeetCode-837-新21点-Python

837. 新 21 点

题目

解题思路

代码实现

实现结果

总结