一道动态规划题目的反思

前言

前几天在刷这道题目的时候遇到不少的问题，现在来对自己的解题进行一些反思。

题目描述

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

题目分析

看到这道题目，我们不难想到根据停止抽取的前一次情况开始分析。
（1）所以我们假定 F(X) 为每次从 1-W 个数中进行抽取，当抽取的数字和不小于(>=) X 时抽取停止，最后抽取的数字为 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
可能会有人说了，这不是一个表达式，根据变量值分的两种情况吗？

反思

我刚开始也是这么考虑的。后来，在与小伙伴的探讨过程中，我才意识到：在动态规划中，不存在根据变量值的取值范围，适用递推公式不同的情况。动态规划一定是将一个大问题分为若干个解决方案相同的小问题，最后根据小问题的解，得到大问题的答案。
在这道题当中，递推公式是T(X)，而在求解T(X)过程中需要的F(X)值，可以根据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;
    }
}