LeetCode 837. New 21 Game

837. New 21 Game

解题思路

概率论问题，一般概率论的问题，需要有两部分，第一是概率推导公式，第二是初始或者最终的状态。通过两个过程和某个状态，求要求的概率值。
我们定义f[i]是从i开始抽卡片，获胜的概率。
根据题意，当i >= K && i <= N的时候，获胜的概率是1。当i > N的时候，获胜的概率是0。【最终状态】
由于每次抽牌有W种可能，因此f[i] = (f[i + 1] + f[i + 2] + … + f[i + W]) / W。
该公式是O(n)的，由于题目是10000的范围，LeetCode会超时。因此继续优化。
f[i + 1] = (f[i + 2] + f[i + 3] + … + f[i + W + 1]) / W。和f[i]做差，得到如下式子：
f[i] = f[i + 1] + (f[i + 1] - f[i + W + 1]) / W。【概率推导公式】
该公式成立的条件是，f[i]和f[i + 1]都需要满足上述概率公式，当i = K - 1的时候， i + 1 = K的概率值是内定的，所以不能通过上述式子直接求，必须按照O(n)的式子求一下。
代码如下：

代码

class Solution {
public:
    vector<double> f;
    double new21Game(int N, int K, int W) {
        if (K == 0) {
            return 1;
        }
        f = vector<double>(20010, 0);
        for (int i = K; i <= N; i ++) {
            f[i] = 1;
        }
        for (int i = 1; i <= W; i ++) {
            f[K - 1] += f[K - 1 + i] / W;
        }
        for (int i = K - 2; i >= 0; i --) {
            f[i] = f[i + 1] + (f[i + 1] - f[i + W + 1]) / W;
        }
        return f[0];
    }
};