LeetCode.837 - 新21点

题目

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

解法：动态规划

令 dp[x] 表示从分数为 x 的状态开始游戏，最终得分不超过 N 的概率。则本题的目的是求 dp[0].
考虑到不超过K的最高得分为 K-1，由于分数超过 K 就结束游戏，而从当前的 K-1 分再抽一次数字不小于 K 且不超过 N 的分数区间为 [K, min(N, K + W - 1)]。这里min在两种情况中取小：1)像示例中的抽W=10的前6种可能分数不会超过N；2)在 K-1 的状态下即使抽到最大的点数W也不会超过N。
这样，当 \(K \leq x \leq \min (N, K+W-1)\) 让dp[x]=1，\(x>\min (N, K+W-1)\) 让dp[x]=0。基于此，可以得到 \(0 \leq x < K\) 时的转移方程：

\[dp[x] = \frac{dp[x+1] + dp[x+2] + dp[x+W]}{W} \]

可以在每次计算 dp[x]的时候从 dp[x+1] 累加到 dp[x+W]，但这中间显然存在重复计算。因此可以简化一下计算，对dp的相邻项做差：

\[dp[x]-dp[x+1]=\frac{dp[x+1]-dp[x+W+1]}{W} \]

这样就得到新的转移方程：

\[dp[x]=dp[x+1] + \frac{dp[x+1]-dp[x+W+1]}{W} \]

注意 \(0 \leq x <K-1\)
所以这里dp[K-1]需要单独计算一下：
由于只有当 \(K \leq x \leq \min (N, K+W-1)\) 时 dp[x]=1，所以很容易得到\(dp[K-1] = \frac{min(N, K + W - 1) - (K-1)}{W} = \frac{min(N-K+1, W)}{W}\)

class Solution {
    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;  // 注意 * 1.0 做类型转换
        for(int i = K - 2; i >= 0; i--){
            dp[i] = dp[i + 1] - (dp[i + 1 + W] - dp[i + 1]) / W;
        }
        return dp[0];
    }
}

LeetCode.837 - 新21点

题目

解法：动态规划

推荐阅读