算法：新21点

算法

发布日期: 2020-06-03

题目：新21点

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：

爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。每次抽取都是独立的，其结果具有相同的概率。

当爱丽丝获得不少于 K 分时，她就停止抽取数字。爱丽丝的分数不超过 N 的概率是多少？

示例 1：

1
2
3

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

示例 2：

输入：N = 6, K = 1, W = 10
输出：0.60000
说明：爱丽丝得到一张卡，然后停止。
在 W = 10 的 6 种可能下，她的得分不超过 N = 6 分。

示例 3：

1 2	输入：N = 21, K = 17, W = 10 输出：0.73278

提示：

1 2	0 <= K <= N <= 10000 1 <= W <= 10000

如果答案与正确答案的误差不超过 10^-5，则该答案将被视为正确答案通过。
此问题的判断限制时间已经减少。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/new-21-game

分析

详细题解可前往上述力扣官网查看。此处我讲解我做题的思路和一些个人总结等

首先要做的就是理解题意，知道难点在哪。我当时做这道题，就是因为不理解题意。我们可以使用暴力推算来一步步看具体计算逻辑，再进行化简。暴力算法不是没用，他是一切优化算法的基石。

拿一个例子：k=5，n=7，w=,4。

首先要理解这个游戏是怎么玩的，我们可以一直抽牌，牌的大小在[1,w]，如果手上的点数不超过k，那么必须继续抽，如果超过了，就停下来。然后看看手上的点数此时是否超过了n。（默认每次抽到任何点数的概率相同）
算概率，我们先算样本空间。最大值是k-1+w。因为k的话已经满足了，那么当手上的点数是k-1且抽到最大点数的牌w，那么就是k-1+w。最小值毋庸置疑就是k了。
这样基本上我们就了解整个题意了。然后看看怎么暴力解决它。大于k的时候已经没办法抽了，所以我们考虑小于k的情况。当手上的点数是k-1时，那么可能的结果就是[k,k-1+w]，且每个结果概率相等。然后求小于n的概率，那是不是很容易就可以求出来了。古典概率模型嘛。例如上面的例子，当手上的点数是4的时候，那么小于等于8就只有5,6,7；剩下的8，就不行了，所以概率是0.75.来我们继续。也就是从4出发的话，概率是0.75.那我们看看从3出发，概率是多少。
从3出发可能的范围是[4,8]，然后4的概率我们已经知道了是0.75，然后5,6,7,8都是小于n的，那么3出发的概率就是0.750.25+0.75。是不是已经发现什么了？只要这样一直往前推，推导第一位那答案不是就出来了？而且每一个答案都和前面的答案有关？是不是闻到了一股熟悉的味道？对就是*动态规划**
按照上面的思路我们只需要一步步往前推。接下来是我们要确定状态转移方程。从上面我们可以发现 P(3) = 1/4 * P(4) + 3/4 * [P(4)-P(3+4)] 。然后把里面一些数字用循环的i变量和参数代替就可以了。

个人思考：一定要先理解题意然后用暴力解法思考一下，不要一开始就想着套用什么模板。暴力解法之后才知道题目的本质是什么，然后用什么方法可以简化。然后再运用动态规划，滑动窗口等等方法去解决。

代码实现

public double new21Game(int N, int K, int W) {
    if (K == 0) {
        return 1.0;
    }
    double[] dp = new double[K + W];
    for (int i = K; i <= N && i < K + W; i++) {
        dp[i] = 1.0;
    }
    dp[K - 1] = 1.0 * Math.min(N - K + 1, W) / W;
    for (int i = K - 2; i >= 0; i--) {
        dp[i] = dp[i + 1] - (dp[i + W + 1] - dp[i + 1]) / W;
    }
    return dp[0];
}