前言

前幾天在刷這道題目的時候遇到不少的問題，現(xiàn)在來對自己的解題進行一些反思。

題目描述

愛麗絲參與一個大致基于紙牌游戲 “21點” 規(guī)則的游戲，描述如下：
愛麗絲以 0 分開始，并在她的得分少于 K 分時抽取數(shù)字。 抽取時，她從 [1, W] 的范圍中隨機獲得一個整數(shù)作為分數(shù)進行累計，其中 W是整數(shù)。 每次抽取都是獨立的，其結果具有相同的概率。
當愛麗絲獲得不少于 K 分時，她就停止抽取數(shù)字。 愛麗絲的分數(shù)不超過 N 的概率是多少？
示例 1：

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

示例 2：

輸入：N = 6, K = 1, W = 10
輸出：0.60000
說明：愛麗絲得到一張卡，然后停止。
在 W = 10 的 6 種可能下，她的得分不超過 N = 6 分。

示例 3：

輸入：N = 21, K = 17, W = 10
輸出：0.7327

題目分析

看到這道題目，我們不難想到根據(jù)停止抽取的前一次情況開始分析。
（1）所以我們假定 F(X) 為每次從 1-W 個數(shù)中進行抽取，當抽取的數(shù)字和不小于(>=) X 時抽取停止，最后抽取的數(shù)字為 X 的概率。
則：F(X) = Sum( F(X-W)/W + F(X-W+1)/W +...+ F(X-1)/W ) X<K
（2）但是對于本題來說，我們要考慮一種情況，即上一次的累加值不能取到 X-1 ，也就是 X>=K。我們前一次抽取的累加值最大為 K-1。
則：T(X) = Sum( F(X-W)/W + F(X-W+1)/W +...+ F(K-1)/W ) X>=K && X<=N
可能會有人說了，這不是一個表達式，根據(jù)變量值分的兩種情況嗎？

反思

我剛開始也是這么考慮的。后來，在與小伙伴的探討過程中，我才意識到：在動態(tài)規(guī)劃中，不存在根據(jù)變量值的取值范圍，適用遞推公式不同的情況。動態(tài)規(guī)劃一定是將一個大問題分為若干個解決方案相同的小問題，最后根據(jù)小問題的解，得到大問題的答案。
在這道題當中，遞推公式是T(X)，而在求解T(X)過程中需要的F(X)值，可以根據(jù)F(X)表達式得到。

最后

知道這一點后，最后要求解的答案就很容易得到了，只需要累加T(K)一直到T(N)的值即可。

class Solution {
    public double new21Game(int N, int K, int W) {
        if(K==0){
            return 1;
        }
        double[] f1=new double[K];
        double[] f2=new double[W];
        f1[0]=1;
        double count=0;
        for(int i=1;i<K;i++){
            count+=f1[i-1];
            if(i>W) count-=f1[i-W-1];
            f1[i]=count/W;
        }
        double sum=0;
        double res=0;
        int start=K-W>0?K-W:0;
        for(int i=start;i<K;i++){
            sum+=f1[i];
        }
        res=sum;
        int end=K+W-1<=N?K+W-1:N;
        for(int i=K+1;i<=end;i++){
            if(i>W) sum-=f1[i-W-1];
            res+=sum;
        }
        return res/W;
    }
}