[LeetCode]New 21 Game

给定一堆范围为[1, W]的牌，每张等概率抽到。每次抽一张，记录累加和s。如果s大于等于K的话我们停止抽牌，求最后s小于等于N(N >= K)的概率。乍一看是数学题，其实会发现算起来并不容易。或者我们可以用模拟的方法，比如模拟10000次这个过程看小于等于N的概率是多少，但显然不准确。所以我们还是回到分析子问题上来，首先递归的方法很容易想，假设当前和为sum:

• 如果sum > N, return 0
• 如果sum >= K && sum <= N, return 1
• 如果小于K，我们遍历所有的W，那么probability(sum) = 1 / W * probability(sum + 1) + 1 / W * probability(sum + 2) + 1 / W * probability(sum + 3) + ... + 1 / W * probability(sum + W)   

可以看出来这是一个天然的递归。但是时间复杂度太高，为O(W^K)，过不了大的test case。代码如下：


一个优化就是用memorization，避免重复的计算。对于每一个sum我们存下来计算的结果，空间复杂度O(N)，时间复杂度理应也是O(N)但是并过不了全部的test case。代码如下：




DP的方法可以解决这道问题，假设我们计算s = x的概率，那么有以下两种情况：

• 如果x <= W, 那么除了我们可以通过x - 1, x - 2 ... 1抽取1, 2 ... x - 1到达x之外，我们还可以直接抽到x。但是注意x - 1不能大于K，否则我们最大只取到K，因为大于等于K的时候我们停止抽牌
• 如果x > W, 我们不可能直接抽到x。所以我们只能通过x - 1, x -2...x - Wd到达x。同样x - 1不能大于K。

我们用dp[i]表示和为i的概率。所以我们根据这个得到dp公式：

• dp[i] = dp[1] / W + dp[2] / W + ... + dp[min(K - 1, i - 1)] / W + 1.0 / W, if i <= W
• dp[i] = dp[i - W] / W + dp[i - W + 1] / W + ... + dp[min(i - 1, K - 1)] / W, if i > W

我们不用每次去找i的前W个，我们动态地维护区间和即可。时间空间复杂度均为O(n)，代码如下：