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])