题目

新21点
链接可能点不进去，所以我把完整的题目写在了下面。

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一个整数
作为分数进行累计，其中 W 是整数。 每次抽取都是独立的，其结果具有相同的概率。
当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？

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

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

分析

这道题通过率很低。

题目没啥歧义，我们来看看示例1。题目中说了最开始爱丽丝手上是0分。0<=1(k=1)，所以这时候爱丽丝可以从1-10(w=10)中抽一个整数并累加到0上。
那么爱丽丝此时手上就有了以下可能的分数：

1 2 3 4 5 6 7 8 9 10

这些数都>=1，所以爱丽丝游戏结束，那么满足<=10(n=10)的数有10个，所以答案为10/10=1。
如果示例1中k=2呢？那么爱丽丝第一次抽取后得到的分数中的1还需要继续抽取。然后不停的进行游戏，直到所有可能得到的数累加后都>=k为止。
首先我们可以知道以下几点：

1：n肯定>=k，不然答案肯定是0，这个不难想通，而且条件也给出来了；
2：这个游戏在有限步内肯定会停止，因为是从1-w进行抽取，即便最开始分数为0，那么抽k次，
每次都抽到1累加起来也是k，而k>=k，游戏停止。

递归

最开始我们很容易想到一种思路，就是递归，我们抽取一轮后判断哪些数还需要继续抽取。

    double new21Game(int N, int K, int W) {
        if(K == 0) {
            return 1;
        }
        return currNew21Game(0,N,K,W);
    }
    double currNew21Game(int number,int &N, int &K, int &W) {
        //抽到1-W每一个数的概率为1/W
        double everOne = 1.f / W;
        //保存还需要继续抽取的数
        vector<int> numbers;
        //记录累加后>=k的数中有多少个<=n，<=k表示不再继续抽取
        int noThanN = 0;
        for (int num = 1; num <= W; num ++) {
            if(num + number < K) {
                numbers.push_back(num + number);
                continue;
            }
            if(num + number <= N) {
                noThanN ++;
            }
        }
        //记录当前抽取的概率
        double resultCount = 0;
        //概率加上everOne*noThanN，这个不难理解
        resultCount += noThanN * everOne;
        //需要继续抽取的数就是进行递归，但是要乘everOne，这个也很好理解
        for (int index = 0; index < numbers.size(); index ++) {
            resultCount += everOne * currNew21Game(numbers[index],N,K,W);
        }
        return resultCount;
    }

这个思路是正确的，但是条件中说了n<=10000，那么直接宣布死亡，这个肯定是超时。

递归+备忘录

我们可以在递归的思路上加上备忘录

    double new21Game(int N, int K, int W) {
        if(K == 0) {
            return 1;
        }
        unordered_map<int, double> numberMap;
        return currNew21Game(0,N,K,W,numberMap);
    }
    double currNew21Game(int number,int &N, int &K, int &W,unordered_map<int, double> &numberMap) {
        if(numberMap.count(number)) {
            return numberMap[number];
        }
        //抽到1-W每一个数的概率为1/W
        double everOne = 1.f / W;
        //保存还需要继续抽取的数
        vector<int> numbers;
        //记录累加后>=k的数中有多少个<=n
        int noThanN = 0;
        for (int num = 1; num <= W; num ++) {
            if(num + number < K) {
                numbers.push_back(num + number);
                continue;
            }
            if(num + number <= N) {
                noThanN ++;
            }
        }
        //记录当前抽取的概率
        double resultCount = 0;
        //概率加上everOne*noThanN，这个不难理解
        resultCount += noThanN * everOne;
        //需要继续抽取的数就是进行递归，但是要乘everOne，这个也很好理解
        for (int index = 0; index < numbers.size(); index ++) {
            resultCount += everOne * currNew21Game(numbers[index],N,K,W,numberMap);
        }
        numberMap[number] = resultCount;
        return resultCount;
    }

虽然可以加快一点速度，但是还是不行，虽然计算的次数少了，但是递归的次数实在太多了，时间都耗在这里了。

Accept

在经过了一天的坚持不懈后，我发现这道题是在考数学归纳法；说的简单点就是让我们找规律。我是这样思考的。

我们拿n=5,k=4,w=5举例。
题目中有一个条件是误导我们的：起始分数为0，那么我们就会很容易先入为主的认为我们应该从0开始找规律。
但是分数为0会涉及到深层递归的情况，因为第一次抽取后我们会得到1 2 3 4 5，其中的1 2 3我们需要递归；
然后假如我们第一轮得到1，这时我们起始分数为1，第二轮抽取我们就会得到2 3 4 5，其中2 3我们又要进行递归；这样的话我们肯定就绕进去了。所以我们应该逆向思考。
当我们从起始分数为k-1=3时情况就不需要递归，因为我们抽取一次得到的分数为4 5 6 7 8，哇，兄die？是不是很轻松的就得到了概率。因为所有数都>=k了，游戏终止；这时候我们可以直接得到概率为2/5=0.4。
然后我们来推k-2=2时的情况，我们会得到3 4 5 6 7，相对于4 5 6 7 8
我们只需要减去8的概率，再加上3的概率即可，因为3需要递归；但是这个3你发现没有，我们刚才才算过3啊，是不是发现了新大陆？因为我们计算k-2时所有的条件都是已知的了。不要说8不知道。。。
你看到这里的时候你可以自己想一想递归公式了；最后答案就是我们推到0的时候的概率。为什么是0？因为题目说了是从0分开始玩游戏嘛。

    double new21Game(int N, int K, int W) {
        if(K == 0) {
            return 1;
        }
        //我们拿3 2 3举例，可以得到下面的规律
        //假设开始我们的分数为K-1=1，我们可以拿1 2 3，得到的分数为2 3 4，为什么要假设分数为K-1呢，因为这时候没有递归的情况出现，因为肯定都>=K了
        //1-W每个选择的概率
        double everOne = 1.f / W;
        //其中满足<=N的数量是
        int lessNCount = N - K + 1;
        //我们记录算出来的所有开始分数的概率
        double probability[K];
        probability[K - 1] = lessNCount * everOne;
        
        //当开始分数为K-2时，我们得到的是1 2 3，
        //这时候就有两部分了，一部分是>=K的2和3，另一部分是<k的1
        for (int currK = K - 2; currK >= 0; currK --) {
            double currValue = probability[currK + 1];
            //对于5 4 5来说
            //3时得到的是：4 5 6 7 8
            //2时得到的是：3 4 5 6 7
            //也就是说currK是在currK-1的基础上减去currK+W+1，加上currK+1，其中currK+1或者currK+W+1都是我们已经计算过的
            currValue += (everOne * currValue);
            //满足这个条件说明减去的数是在<=n范围内，>n的数不会加到结果概率中的，内部为什么要乘everOne?因为你选到这个数的概率就是这么多，我们当前需要乘了。
            if(currK + W + 1 <= N) {
                //满足这个条件说明减去的数是递归获得的，因为分数<k会继续抽取
                if(currK + W + 1 < K) {
                    currValue -= everOne * probability[currK + W + 1];
                }
                //否则就是>=k，也就是不需要继续抽取的情况，那么概率是一个固定值
                else {
                    currValue -= everOne * 1;
                }
            }
            probability[currK] = currValue;
        }
        return probability[0];
    }

后记