837. New 21 Game

Medium

Description

Alice 玩遊戲，起始 0 分。每次隨機獲得 [1, maxPts] 中的一個分數。當總分 >= k 時停止。求最終總分 <= n 的機率。

Example:

Input: n = 10, k = 1, maxPts = 10 Output: 1.00000

Intuition#

反向 DP + 滑動窗口：dp[i] 是分數為 i 時最終不超過 n 的機率，用窗口和避免重複計算。

dp[i] = 總分為 i 時，最終分數 <= n 的機率
若 i >= k（已停止）：dp[i] = 1 if i <= n，else 0
若 i < k（還在抽）：dp[i] = avg(dp[i+1], dp[i+2], ..., dp[i+maxPts])
用滑動窗口維護連續 maxPts 個 dp 值的和

Approaches#

1: Basic DP (without sliding window)#

概念: 直接計算每個分數的機率，每次遍歷 maxPts 個後繼
時間複雜度: O(k * maxPts)
空間複雜度: O(k + maxPts)

class Solution {
    fun new21Game(n: Int, k: Int, maxPts: Int): Double {
        if (k == 0 || n >= k + maxPts - 1) return 1.0
        val dp = DoubleArray(k + maxPts)
        for (i in k..minOf(n, k + maxPts - 1)) dp[i] = 1.0
        for (i in k - 1 downTo 0) {
            var sum = 0.0
            for (j in 1..maxPts) sum += dp[i + j]
            dp[i] = sum / maxPts
        }
        return dp[0]
    }
}

⭐2: DP + Sliding Window#

概念: 用滑動窗口和維護 dp[i+1..i+maxPts] 的總和，O(1) 更新
時間複雜度: O(k + maxPts)
空間複雜度: O(k + maxPts)

class Solution {
    fun new21Game(n: Int, k: Int, maxPts: Int): Double {
        if (k == 0 || n >= k + maxPts - 1) return 1.0
        val dp = DoubleArray(k + maxPts)
        for (i in k..minOf(n, k + maxPts - 1)) dp[i] = 1.0

        // 初始化窗口和：dp[k] 到 dp[k + maxPts - 1]
        var windowSum = 0.0
        for (i in k until k + maxPts) windowSum += dp[i]

        for (i in k - 1 downTo 0) {
            dp[i] = windowSum / maxPts
            // 滑動窗口：加入 dp[i]，移除 dp[i + maxPts]
            windowSum += dp[i] - dp[i + maxPts]
        }
        return dp[0]
    }
}

🔑 Takeaways#

Pattern: 機率 DP + 滑動窗口 — 狀態轉移是連續區間的平均值
關鍵技巧: 反向 DP（從 k 往 0 算）避免正向計算的複雜依賴；滑動窗口把每步的 O(maxPts) 降到 O(1)