【Day 44 】2023-03-29 - 837. 新 21 点

[azl397985856]

837. 新 21 点

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/new-21-game

前置知识

暂无

题目描述

爱丽丝参与一个大致基于纸牌游戏 “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.73278
 

提示：

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

[JiangyanLiNEU]

class Solution: def new21Game(self, n: int, k: int, maxPts: int) -> float: dp = collections.deque([float(i <= n) for i in range(k, k + maxPts)]) s = sum(dp) for i in range(k): dp.appendleft(s / maxPts) s += dp[0] - dp.pop()

    return dp[0]

[kofzhang]

思路

动态规划，从后向前，依次计算概率（因为前面的牌面依赖后面的点数概率）

复杂度

时间复杂度：O(k+maxPts) 空间复杂度：O(k+maxPts)

代码

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp=[0]*(k+maxPts)
        s = 0  # 右边maxpts张牌的概率累积
        for i in range(k,k+maxPts):
            dp[i] = 1 if i<=n else 0
            s += dp[i]
        for i in range(k-1,-1,-1):
            dp[i]=1/maxPts*s
            s = s - dp[i+maxPts] + dp[i]
        return dp[0]

[wangzh0114]

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        vector<double> dp(k + maxPts);
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        dp[k - 1] = 1.0 * min(n - k + 1, maxPts) / maxPts;
        for (int i = k - 2; i >= 0; i--) {
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
        }
        return dp[0];
    }
};

• TC:O(min(n,k+maxPts))
• SC:O(k+maxPts)

[linlizzz]

思路

滑动窗口+动态规划

代码

(看了官方题解)

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp = [0] * (k + maxPts)
        win_sum = 0
        for i in range(k, k + maxPts):
            if i <= n:
                dp[i] = 1
            win_sum += dp[i]

        for i in range(k - 1, -1, -1):
            dp[i] = win_sum / maxPts
            win_sum += dp[i] - dp[i + maxPts]
        return dp[0]

复杂度分析

T(n) = O(w+k)

S(n) = O(w+k)

[Abby-xu]

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp = [0 for i in range(k)] + [1 for i in range(k, 1 + n)] + [0 for i in range(maxPts)] 
        Win = float(sum(dp[k : k + maxPts])) 
        for i in range(k-1,-1,-1):
            dp[i] = Win / maxPts
            Win += dp[i] - dp[i + maxPts]
        return dp[0]

[huizsh]

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        # 滑动窗口优化（固定窗口大小为 W 的滑动窗口）
        dp = [0] * (K + W)
        win_sum = 0
        for i in range(K, K + W):
            if i <= N:
                dp[i] = 1
            win_sum += dp[i]

        for i in range(K - 1, -1, -1):
            dp[i] = win_sum / W
            win_sum += dp[i] - dp[i + W]
        return dp[0]

[FireHaoSky]

思路：

"""
二分法，从k-1的时候开始计算后续可能结果的概率，并进行累加
"""

代码：python

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp = [0] * (k+maxPts)
        s = 0
        for i in range(k, k+maxPts):
            dp[i] = 1 if i <= n else 0
            s+=dp[i]
        for i in range(k-1,-1,-1):
            dp[i] = s/maxPts
            s = s-dp[i+maxPts]+dp[i]
        return dp[0]

复杂度分析：

"""
时间复杂度：O(k+maxPts)
空间复杂度：O(k+maxPts)
"""

[aoxiangw]

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp = [0.0] * (k + maxPts)
        for i in range(k, min(n + 1, k + maxPts)):
            dp[i] = 1.0
        s = min(n - k + 1,maxPts)
        for j in range(k -1, -1, -1):
            dp[j] = s/float(maxPts)
            s += dp[j] - dp[j + maxPts]
        return dp[0]

time, space: O(n+1)/O(k+maxPts), O(k + maxPts)

[wangqianqian202301]

思路

dp + huadongchuangkou

代码

        if k == 0 or n >= k + maxPts - 1:
            return 1.0
        dp = [0] * (n + 1)
        weight = 1.0
        response = 0.0
        dp[0] = 1.0
        for i in range(1, n + 1):
            dp[i] = weight / maxPts
            if i < k:
                weight = weight + dp[i]
            else:
                response = response + dp[i]
            if i - maxPts >= 0:
                weight = weight - dp[i - maxPts]
        return response

复杂度

O(n)

[harperz24]

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0:
            return 1.0

        dp = [0.0] * (k + maxPts)
        for i in range(k, min(n, k + maxPts - 1) + 1):
            dp[i] = 1.0

        dp[k - 1] = float(min(n - k + 1, maxPts)) / maxPts

        for i in range(k - 2, -1, -1):
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts
        return dp[0]

[JasonQiu]

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp = [1 if i <= N else 0 for i in range(k + maxPts)]
        s = sum(dp[k:(k + maxPts)])
        for i in range(k - 1, -1, -1):
            dp[i] = s / maxPts
            s -= dp[i + maxPts] + dp[i]
        return dp[0]

[Meisgithub]

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0)
        {
            return 1.0;
        }
        vector<double> dp(k + maxPts);
        for (int i = k; i <= n && i < k + maxPts; i++)
        {
            dp[i] = 1.0;
        }
        dp[k - 1] = 1.0 * min(n - k + 1, maxPts) / maxPts;
        for (int i = k - 2; i >= 0; i--)
        {
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
        }
        return dp[0];
    }
};

[jackgaoyuan]

func new21Game(n int, k int, maxPts int) float64 {
    dp := make([]float64, k + maxPts)
    for i := k; i < k + maxPts; i++ {
        if i <= n {
            dp[i] = 1
        } else {
            dp[i] = 0
        }
    }
    for i := k - 1; i >= 0; i-- {
        var sum float64
        for j := i + 1; j <= i + maxPts; j++ {
            sum += dp[j]
        }
        dp[i] = sum / float64(maxPts)
    }
    return dp[0]
}

[jackgaoyuan]

func new21Game(n int, k int, maxPts int) float64 {
    dp := make([]float64, k + maxPts)
    for i := k; i < k + maxPts; i++ {
        if i <= n {
            dp[i] = 1
        } else {
            dp[i] = 0
        }
    }
    for i := k - 1; i >= 0; i-- {
        var sum float64
        for j := i + 1; j <= i + maxPts; j++ {
            sum += dp[j]
        }
        dp[i] = sum / float64(maxPts)
    }
    return dp[0]
}

[Hughlin07]

class Solution {

public double new21Game(int n, int k, int maxPts) {
    if(k==0) return 1.00;
    if(k==1 && maxPts<=n) return 1.00;
    double dp[] = new double[n+1];
    dp[0] = 1.00;
    double prev=0.00;
    for(int i=1; i<=n; i++){
        if((i-maxPts-1)>=0){
            prev-=dp[i-1-maxPts];
        }
        if((i-1)<k){
            prev+=dp[i-1];
        }
        dp[i]=prev/maxPts;            
    }

    double res = 0.00;
    for(int i=k; i<=n; i++){
        res+=dp[i];
    }
    return res;        
}

}

[NorthSeacoder]

/**
 * @param {number} n
 * @param {number} k
 * @param {number} maxPts
 * @return {number}
 */
var new21Game = function(n, k, maxPts) {
    const dp = new Array(k + maxPts).fill(0);
    let sum = 0;
    for (let i = k; i <= n && i < k + maxPts; i++) {
        dp[i] = 1;
        sum++;
    }

    for (let i = k - 1; i >= 0; i--) {
        dp[i] = sum / maxPts;
        sum += dp[i] - dp[i + maxPts];
    }

    return dp[0];
};

• TC: O(k*maxPts)
• SC:O(k+maxPts)

[bookyue]

TC: O(n+maxPts)
SC: O(n+maxPts)

    public double new21Game(int n, int k, int maxPts) {
        if (k == 0) return 1;

        double[] dp = new double[k + maxPts];
        double sum = 0;
        for (int i = k; i < k + maxPts; i++) {
            if (i <= n) dp[i] = 1;
            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];
    }

[joemonkeylee]

思路

不是很懂dp。。 先抄一个。。一会儿写滑动窗口+二分

代码

     public double New21Game(int n, int k, int maxPts)
        {
            if (k == 0)
            {
                return 1.0;
            }
            double[] dp = new double[k + maxPts];
            for (int i = k; i <= n && i < k + maxPts; i++)
            {
                dp[i] = 1.0;
            }
            dp[k - 1] = 1.0 * Math.Min(n - k + 1, maxPts) / maxPts;
            for (int i = k - 2; i >= 0; i--)
            {
                dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
            }
            return dp[0];
        }

复杂度分析

• 时间复杂度：O(min(n,k+maxPts))
• 空间复杂度：O(k+maxPts)

[tzuikuo]

思路

待定

代码

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0 || n >= k + maxPts - 1) return 1.0;
        vector<double> dp(n + 1);
        dp[0] = 1.0;
        double W = 1.0, res = 0.0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = W / maxPts;
            if (i < k) W += dp[i];
            else res += dp[i];
            if (i - maxPts >= 0) W -= dp[i - maxPts];
        }
        return res;
    }
};

复杂度分析 待定

[kangliqi1]

public double new21Game(int n, int k, int maxPts) { if(k==0) return 1.00; if(k==1 && maxPts<=n) return 1.00; double dp[] = new double[n+1]; dp[0] = 1.00; double prev=0.00; for(int i=1; i<=n; i++){ if((i-maxPts-1)>=0){ prev-=dp[i-1-maxPts]; } if((i-1)<k){ prev+=dp[i-1]; } dp[i]=prev/maxPts;
}

double res = 0.00;
for(int i=k; i<=n; i++){
    res+=dp[i];
}
return res;        

}

[yingchehu]

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        dp = [0] * (K + W)
        win_sum = 0
        for i in range(K, K + W):
            if i <= N:
                dp[i] = 1
            win_sum += dp[i]

        for i in range(K - 1, -1, -1):
            dp[i] = win_sum / W
            win_sum += dp[i] - dp[i + W]
        return dp[0]

[CruiseYuGH]

关键点

代码

• 语言支持：Python3

Python3 Code:

class Solution:
     def new21Game(self, N: int, K: int, W: int) -> float:
        # 滑动窗口优化（固定窗口大小为 W 的滑动窗口）
        dp = [0] * (K + W)
        win_sum = 0
        for i in range(K, K + W):
            if i <= N:
                dp[i] = 1
            win_sum += dp[i]

        for i in range(K - 1, -1, -1):
            dp[i] = win_sum / W
            win_sum += dp[i] - dp[i + W]
        return dp[0]

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$

[Fuku-L]

代码

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

复杂度分析

• 时间复杂度：O(min(n, k+ maxPts))
• 空间复杂度：O(k+maxPts)

[lp1506947671]

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        dp = [0] * (K + W)
        for i in range(K, K + W):
            if i <= N:
                dp[i] = 1

        for i in range(K - 1, -1, -1):
            dp[i] = sum(dp[i + j] for j in range(1, W + 1)) / W
        return dp[0]

复杂度分析

• 时间复杂度：O(KW)
• 空间复杂度：O(K+W)

[Lydia61]

837. 新21点

思路

滑动窗口、动态规划

代码

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0:
            return 1.0
        dp = [0.0] * (k + maxPts)
        for i in range(k, min(n, k + maxPts - 1) + 1):
            dp[i] = 1.0
        dp[k - 1] = float(min(n - k + 1, maxPts)) / maxPts
        for i in range(k - 2, -1, -1):
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts
        return dp[0]

复杂度分析

• 时间复杂度：O(min(n, MaxPts))
• 空间复杂度：O(min(k, MaxPts))

[AstrKing]

class Solution { public double new21Game(int N, int K, int W) { if (K == 0 || N >= K + W) return 1; double dp[] = new double[N + 1], Wsum = 1, res = 0; dp[0] = 1; for (int i = 1; i <= N; ++i) { dp[i] = Wsum / W; if (i < K) Wsum += dp[i]; else res += dp[i]; if (i - W >= 0) Wsum -= dp[i - W]; } return res; } }

[RestlessBreeze]

code

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        vector<double> dp(k + maxPts);
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        dp[k - 1] = 1.0 * min(n - k + 1, maxPts) / maxPts;
        for (int i = k - 2; i >= 0; i--) {
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
        }
        return dp[0];
    }
};

[snmyj]

class Solution(object): def new21Game(self, N, K, W):

    if K == 0: return 1
    dp = [1.0] + [0] * N
    tSum = 1.0
    for i in range(1, N + 1):
        dp[i] = tSum / W
        if i < K:
            tSum += dp[i]
        if 0 <= i - W < K:
            tSum -= dp[i - W]
    return sum(dp[K:])

[jmaStella]

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        if (n-k + 1 >= maxPts) {
            return 1.0;
        }
        double[] dp = new double[k+maxPts];
        double sum = n-k+1;
        for(int i=k; i<=n; i++){
            dp[i] =1;
        }

        for(int i=k-1; i>=0; i--){
            dp[i] = sum / (maxPts);
            sum = sum - dp[i+maxPts]+ dp[i];
        }
        return dp[0];
    }
}

[Jetery]

class Solution {
public:
    double new21Game(int N, int K, int W) {
        if (K == 0) return 1.0;

        vector<double> f(N + 1, 0), s(N + 1, 0);
        f[0] = s[0] = 1;

        for (int i = 1; i <= N; i++) {
            int l = max(0, i - W), r = min(K - 1, i - 1);

            if (l <= r) {
                if (l == 0) f[i] = s[r] / W;
                else f[i] = (s[r] - s[l - 1]) / W;
            }

            s[i] = s[i - 1] + f[i];
        }

        return s[N] - s[K - 1];
    }
};

[DrinkMorekaik]

var new21Game = function (n, k, w) {
    const dp = new Array(k + w).fill(0)
    for (let i = k; i <= Math.min(n, k - 1 + w); i++) {
        dp[i] = 1
    }
    for (let i = k - 1; i >= 0; i--) {
        sum = 0
        for (let j = 1; j <= w; j++) {
            sum += dp[i + j]
        }
        dp[i] = sum / w
    }

    return dp[0]
};

[X1AOX1A]

蒙特卡洛模拟（超时，图一乐）

import random

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        # get random bonus between [1, maxPts]
        def get_random_bonus(maxPts, sample_size):            
            return [random.randint(1, maxPts) for _ in range(sample_size)]

        # 获得 k 分 或更多分时，停止抽取数字
        def get_indicator(points, k):
            return [point<k for point in points]

        def Monte_Carlo(points, maxPts, k, epochs, sample_size):
            for _ in range(epochs):
                bonus = get_random_bonus(maxPts, sample_size)
                indicators = get_indicator(points, k)
                if sum(indicators)==0: return points
                points = [b*i+p for (b, i, p) in zip(bonus, indicators, points)]
            return points

        epochs = 100000
        sample_size = 100000
        points = [0]*sample_size # init points
        points = Monte_Carlo(points, maxPts, k, epochs, sample_size)

        # 分数不超过 n 的概率
        return sum([point<=n for point in points]) / sample_size

• 时间复杂度：O(epochs*sample_size)
• 空间复杂度：O(sample_size)

[chanceyliu]

代码

function new21Game(n: number, k: number, maxPts: number): number {
  let dp = new Array(k + maxPts).fill(0);
  dp[n] = 1;
  for (let i = n - 1; i >= 0; i--) {
    if (i >= k && i <= n) {
      dp[i] = 1;
    }
    if (i < k) {
      for (let j = 1; j <= maxPts; j++) {
        if (i + j <= n) {
          dp[i] += dp[i + j] / maxPts;
        }
      }
    }
  }
  return dp[0];
}

[duke-github]

思路

动态规划

代码

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        double[] dp = new double[k + maxPts];
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        for (int i = k - 1; i >= 0; i--) {
            for (int j = 1; j <= maxPts; j++) {
                dp[i] += dp[i + j] / maxPts;
            }
        }
        return dp[0];
    }
}