Medium

题目描述

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏。

爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。 在每次抽取中，她获得一个范围为 [1, maxPts] 的整数的点数，其中 maxPts 是一个整数。每次抽取都是独立的，其结果具有相等的概率。

当爱丽丝获得 k 分或更多分时，她就停止抽取数字。

返回爱丽丝得分不超过 n 的概率。

与实际答案误差不超过 10-5 的答案将被视为正确答案。

示例 1：

输入：n = 10, k = 1, maxPts = 10
输出：1.00000
解释：爱丽丝得到一张卡后就停止。

示例 2：

输入：n = 6, k = 1, maxPts = 10
输出：0.60000
解释：爱丽丝得到一张卡后就停止。在 10 种可能性中，有 6 种她的得分不超过 6 分。

示例 3：

输入：n = 21, k = 17, maxPts = 10
输出：0.73278

约束条件：

  • 0 <= k <= n <= 10^4
  • 1 <= maxPts <= 10^4

解题思路

这是一个概率动态规划问题。我们需要计算爱丽丝最终得分不超过 n 的概率。

核心思路：

  1. 定义 dp[i] 为从得分 i 开始，最终得分不超过 n 的概率
  2. 当 i >= k 时，游戏结束，如果 i <= n 则概率为 1，否则为 0
  3. 当 i < k 时，需要继续抽牌，转移方程为：dp[i] = (dp[i+1] + dp[i+2] + ... + dp[i+maxPts]) / maxPts

优化策略： 由于状态转移涉及连续区间求和，我们可以使用滑动窗口技巧来优化：

  • 维护一个和 sum，表示当前窗口内所有概率的和
  • 当计算 dp[i] 时，dp[i] = sum / maxPts
  • 然后更新窗口：移除 dp[i+maxPts+1]，添加 dp[i]

这样可以将时间复杂度从 O(k×maxPts) 优化到 O(k+maxPts)。

边界处理：

  • 如果 k == 0 或 n >= k + maxPts - 1，概率为 1
  • 从后往前计算，确保依赖的状态已经计算完毕

代码实现

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0 || n >= k + maxPts - 1) {
            return 1.0;
        }
        
        vector<double> dp(k + maxPts, 0.0);
        
        // 初始化边界条件
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        
        // 滑动窗口求和
        double sum = 0.0;
        for (int i = k; i < k + maxPts; i++) {
            sum += dp[i];
        }
        
        // 从后往前计算
        for (int i = k - 1; i >= 0; i--) {
            dp[i] = sum / maxPts;
            sum = sum - dp[i + maxPts] + dp[i];
        }
        
        return dp[0];
    }
};

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k + maxPts - 1:
            return 1.0
        
        dp = [0.0] * (k + maxPts)
        
        # 初始化边界条件
        for i in range(k, min(n + 1, k + maxPts)):
            dp[i] = 1.0
        
        # 滑动窗口求和
        sum_prob = sum(dp[k:k + maxPts])
        
        # 从后往前计算
        for i in range(k - 1, -1, -1):
            dp[i] = sum_prob / maxPts
            sum_prob = sum_prob - dp[i + maxPts] + dp[i]
        
        return dp[0]

public class Solution {
    public double New21Game(int n, int k, int maxPts) {
        if (k == 0 || n >= k + maxPts - 1) {
            return 1.0;
        }
        
        double[] dp = new double[k + maxPts];
        
        // 初始化边界条件
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        
        // 滑动窗口求和
        double sum = 0.0;
        for (int i = k; i < k + maxPts; i++) {
            sum += dp[i];
        }
        
        // 从后往前计算
        for (int i = k - 1; i >= 0; i--) {
            dp[i] = sum / maxPts;
            sum = sum - dp[i + maxPts] + dp[i];
        }
        
        return dp[0];
    }
}

var new21Game = function(n, k, maxPts) {
    if (k == 0 || n >= k + maxPts - 1) return 1.0;
    
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1.0;
    
    let windowSum = 1.0;
    
    for (let i = 1; i <= n; i++) {
        dp[i] = windowSum / maxPts;
        
        if (i < k) {
            windowSum += dp[i];
        }
        
        if (i - maxPts >= 0) {
            windowSum -= dp[i - maxPts];
        }
    }
    
    let result = 0;
    for (let i = k; i <= n; i++) {
        result += dp[i];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(k + maxPts)
空间复杂度O(k + maxPts)