題目

新21點(diǎn)
鏈接可能點(diǎn)不進(jìn)去凌彬，所以我把完整的題目寫在了下面。

愛麗絲參與一個(gè)大致基于紙牌游戲 “21點(diǎn)” 規(guī)則的游戲循衰，描述如下：
愛麗絲以 0 分開始铲敛，并在她的得分少于 K 分時(shí)抽取數(shù)字。 抽取時(shí)羹蚣，她從 [1, W] 的范圍中隨機(jī)獲得一個(gè)整數(shù)
作為分?jǐn)?shù)進(jìn)行累計(jì)原探，其中 W 是整數(shù)。 每次抽取都是獨(dú)立的顽素，其結(jié)果具有相同的概率咽弦。
當(dāng)愛麗絲獲得不少于 K 分時(shí)，她就停止抽取數(shù)字胁出。 愛麗絲的分?jǐn)?shù)不超過 N 的概率是多少型型？

示例 1：
輸入：N = 10, K = 1, W = 10
輸出：1.00000
說明：愛麗絲得到一張卡，然后停止全蝶。

提示：
0 <= K <= N <= 10000
1 <= W <= 10000
如果答案與正確答案的誤差不超過 10^-5闹蒜，則該答案將被視為正確答案通過寺枉。
此問題的判斷限制時(shí)間已經(jīng)減少。

分析

這道題通過率很低绷落。

題目沒啥歧義姥闪，我們來看看示例1。題目中說了最開始愛麗絲手上是0分砌烁。0<=1(k=1)筐喳，所以這時(shí)候愛麗絲可以從1-10(w=10)中抽一個(gè)整數(shù)并累加到0上。
那么愛麗絲此時(shí)手上就有了以下可能的分?jǐn)?shù)：

1 2 3 4 5 6 7 8 9 10

這些數(shù)都>=1函喉，所以愛麗絲游戲結(jié)束避归，那么滿足<=10(n=10)的數(shù)有10個(gè)，所以答案為10/10=1管呵。
如果示例1中k=2呢梳毙？那么愛麗絲第一次抽取后得到的分?jǐn)?shù)中的1還需要繼續(xù)抽取。然后不停的進(jìn)行游戲捐下，直到所有可能得到的數(shù)累加后都>=k為止账锹。
首先我們可以知道以下幾點(diǎn)：

1：n肯定>=k，不然答案肯定是0蔑担，這個(gè)不難想通牌废，而且條件也給出來了耳鸯；
2：這個(gè)游戲在有限步內(nèi)肯定會停止冰悠，因?yàn)槭菑?-w進(jìn)行抽取未状，即便最開始分?jǐn)?shù)為0，那么抽k次排抬，
每次都抽到1累加起來也是k，而k>=k授段，游戲停止蹲蒲。

遞歸

最開始我們很容易想到一種思路，就是遞歸侵贵，我們抽取一輪后判斷哪些數(shù)還需要繼續(xù)抽取届搁。

    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每一個(gè)數(shù)的概率為1/W
        double everOne = 1.f / W;
        //保存還需要繼續(xù)抽取的數(shù)
        vector<int> numbers;
        //記錄累加后>=k的數(shù)中有多少個(gè)<=n，<=k表示不再繼續(xù)抽取
        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 ++;
            }
        }
        //記錄當(dāng)前抽取的概率
        double resultCount = 0;
        //概率加上everOne*noThanN窍育，這個(gè)不難理解
        resultCount += noThanN * everOne;
        //需要繼續(xù)抽取的數(shù)就是進(jìn)行遞歸卡睦，但是要乘everOne，這個(gè)也很好理解
        for (int index = 0; index < numbers.size(); index ++) {
            resultCount += everOne * currNew21Game(numbers[index],N,K,W);
        }
        return resultCount;
    }

這個(gè)思路是正確的漱抓，但是條件中說了n<=10000表锻，那么直接宣布死亡，這個(gè)肯定是超時(shí)乞娄。

遞歸+備忘錄

我們可以在遞歸的思路上加上備忘錄

    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每一個(gè)數(shù)的概率為1/W
        double everOne = 1.f / W;
        //保存還需要繼續(xù)抽取的數(shù)
        vector<int> numbers;
        //記錄累加后>=k的數(shù)中有多少個(gè)<=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 ++;
            }
        }
        //記錄當(dāng)前抽取的概率
        double resultCount = 0;
        //概率加上everOne*noThanN瞬逊，這個(gè)不難理解
        resultCount += noThanN * everOne;
        //需要繼續(xù)抽取的數(shù)就是進(jìn)行遞歸显歧，但是要乘everOne，這個(gè)也很好理解
        for (int index = 0; index < numbers.size(); index ++) {
            resultCount += everOne * currNew21Game(numbers[index],N,K,W,numberMap);
        }
        numberMap[number] = resultCount;
        return resultCount;
    }

雖然可以加快一點(diǎn)速度确镊，但是還是不行士骤，雖然計(jì)算的次數(shù)少了，但是遞歸的次數(shù)實(shí)在太多了蕾域，時(shí)間都耗在這里了敦间。

Accept

在經(jīng)過了一天的堅(jiān)持不懈后，我發(fā)現(xiàn)這道題是在考數(shù)學(xué)歸納法束铭；說的簡單點(diǎn)就是讓我們找規(guī)律廓块。我是這樣思考的。

我們拿n=5,k=4,w=5舉例契沫。
題目中有一個(gè)條件是誤導(dǎo)我們的：起始分?jǐn)?shù)為0带猴，那么我們就會很容易先入為主的認(rèn)為我們應(yīng)該從0開始找規(guī)律。
但是分?jǐn)?shù)為0會涉及到深層遞歸的情況懈万，因?yàn)榈谝淮纬槿『笪覀儠玫? 2 3 4 5拴清，其中的1 2 3我們需要遞歸；
然后假如我們第一輪得到1会通，這時(shí)我們起始分?jǐn)?shù)為1口予，第二輪抽取我們就會得到2 3 4 5，其中2 3我們又要進(jìn)行遞歸涕侈；這樣的話我們肯定就繞進(jìn)去了沪停。所以我們應(yīng)該逆向思考。
當(dāng)我們從起始分?jǐn)?shù)為k-1=3時(shí)情況就不需要遞歸裳涛，因?yàn)槲覀兂槿∫淮蔚玫降姆謹(jǐn)?shù)為4 5 6 7 8木张，哇，兄die端三？是不是很輕松的就得到了概率舷礼。因?yàn)樗袛?shù)都>=k了，游戲終止郊闯；這時(shí)候我們可以直接得到概率為2/5=0.4妻献。
然后我們來推k-2=2時(shí)的情況，我們會得到3 4 5 6 7团赁，相對于4 5 6 7 8
我們只需要減去8的概率育拨，再加上3的概率即可，因?yàn)?需要遞歸然痊；但是這個(gè)3你發(fā)現(xiàn)沒有至朗，我們剛才才算過3啊，是不是發(fā)現(xiàn)了新大陸剧浸？因?yàn)槲覀冇?jì)算k-2時(shí)所有的條件都是已知的了锹引。不要說8不知道矗钟。。嫌变。
你看到這里的時(shí)候你可以自己想一想遞歸公式了吨艇；最后答案就是我們推到0的時(shí)候的概率。為什么是0腾啥？因?yàn)轭}目說了是從0分開始玩游戲嘛东涡。

    double new21Game(int N, int K, int W) {
        if(K == 0) {
            return 1;
        }
        //我們拿3 2 3舉例，可以得到下面的規(guī)律
        //假設(shè)開始我們的分?jǐn)?shù)為K-1=1倘待，我們可以拿1 2 3疮跑，得到的分?jǐn)?shù)為2 3 4，為什么要假設(shè)分?jǐn)?shù)為K-1呢凸舵，因?yàn)檫@時(shí)候沒有遞歸的情況出現(xiàn)祖娘，因?yàn)榭隙ǘ?gt;=K了
        //1-W每個(gè)選擇的概率
        double everOne = 1.f / W;
        //其中滿足<=N的數(shù)量是
        int lessNCount = N - K + 1;
        //我們記錄算出來的所有開始分?jǐn)?shù)的概率
        double probability[K];
        probability[K - 1] = lessNCount * everOne;
        
        //當(dāng)開始分?jǐn)?shù)為K-2時(shí)，我們得到的是1 2 3啊奄，
        //這時(shí)候就有兩部分了渐苏，一部分是>=K的2和3，另一部分是<k的1
        for (int currK = K - 2; currK >= 0; currK --) {
            double currValue = probability[currK + 1];
            //對于5 4 5來說
            //3時(shí)得到的是：4 5 6 7 8
            //2時(shí)得到的是：3 4 5 6 7
            //也就是說currK是在currK-1的基礎(chǔ)上減去currK+W+1菇夸，加上currK+1琼富，其中currK+1或者currK+W+1都是我們已經(jīng)計(jì)算過的
            currValue += (everOne * currValue);
            //滿足這個(gè)條件說明減去的數(shù)是在<=n范圍內(nèi)，>n的數(shù)不會加到結(jié)果概率中的庄新，內(nèi)部為什么要乘everOne?因?yàn)槟氵x到這個(gè)數(shù)的概率就是這么多鞠眉，我們當(dāng)前需要乘了。
            if(currK + W + 1 <= N) {
                //滿足這個(gè)條件說明減去的數(shù)是遞歸獲得的摄咆，因?yàn)榉謹(jǐn)?shù)<k會繼續(xù)抽取
                if(currK + W + 1 < K) {
                    currValue -= everOne * probability[currK + W + 1];
                }
                //否則就是>=k凡蚜，也就是不需要繼續(xù)抽取的情況人断，那么概率是一個(gè)固定值
                else {
                    currValue -= everOne * 1;
                }
            }
            probability[currK] = currValue;
        }
        return probability[0];
    }

后記