【Day 44 】2022-12-14 - 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，则该答案将被视为正确答案通过。
此问题的判断限制时间已经减少。

[Ryanbaiyansong]

''' alice玩游戏, 根据卡牌游戏21点 开始是0点, 随机获得分数[1, maxPts] 得到k or more points的时候停下来 返回的是概率 例子一: k=1, range [1, maxPoints], 即[1,10], n=10, 百分之百比n小 例子二: k=1, range[1, 10], n = 6, 可以抽出来的牌是1,2,3,4,5,6,7,8,9, 10, 小于等于n的概率是6 / 10 = 0.6 例子三: k=17, range[1, 10], n = 21 状态: 如果分数不到k, 游戏不会停止, 最后的ans是分数在k到n之间 假设f[i]为 到达分数i的概率是多少, the probability of reaching at i 距离 maxPts = 6, range = [1, 6], k=18, n=21 所以f[14] = f[13] P(1) + f[12] P(2) + f[11] P(3) + f[10] P(4) + ... + f[8](即f[14 - maxPts]) P(6)(即P(maxPts)) 转换成公式就是f[i] = f[i-1]P(1) + f[i-2]P(2)+f[i-3]P(3) +...+f[i-maxPts]P(maxPts) = f[i-1] (1 / maxPts) + f[i-2] (1 / maxPts)+f[i-3] (1 / maxPts) +...+f[i-maxPts]* (1 / maxPts) = (f[i-1] + f[i-2] + f[i-3] + ... + f[i-maxPts]) / maxPts 这个公式的edge cases是什么呢?

1. 如果求f[3] = f[1] P(2) + f[2] P(1) =》 不适应公式

2. 如果求f[21] = f[20], f[19], f[18] 不可能从这三个状态转移过来, 因为如果分数 >= k, 游戏便会停止 所以只能 = f[17] P(4) + f[16] P(5) + f[15] * P(6)
   ''' ··· class Solution: def new21Game(self, n: int, k: int, maxPts: int) -> float:

   解法一: 未优化, TLE

   # 如果游戏不能开始, 那么一开始的时候总分数就是0, 一定小于=n, 所以返回1
   # if k == 0:
   #     return 1.0
   # # 最大能得到的分数是 k - 1 + maxPts
   # maxScore = k - 1 + maxPts
   # f = [0.0] * (maxScore + 1)
   # # 分数为0的概率是1, 即一张牌都不拿, 那么肯定可以reach point 0
   # f[0] = 1
   # for i in range(1, maxScore + 1):
   #     for j in range(1, maxPts + 1):
   #         # handle edge cases
   #         if i - j >= 0 and i - j < k:
   #             f[i] += f[i-j] / maxPts
   
   # # print(f)
   # return sum(f[i] for i in range(k,n+1))
   
   # 解法二: DP + 滑动窗口
   # 举例, 我们知道
   # f[14] = (f[13] + f[12] + f[11] + f[10] + f[9] + f[8]) / maxPts
   # f[13] =         (f[12] + f[11] + f[10] + f[9] + f[8] + f[7]) / maxPts
   # 
   if k == 0 or maxPts + k <= n:
       return 1.0
   
   f = [0.0] * (n + 1)
   f[0] = 1
   runningSum = f[0]
   res = 0
   for i in range(1, n+1):
       # 假设running sum 已经准备好了
       f[i] = runningSum / maxPts
   
       # 处理窗口的头
       if i < k:
           runningSum += f[i]
       else:
           res += f[i]
   
       # 处理窗口的tail
       if i - maxPts >= 0:
           runningSum -= f[i-maxPts]
   
   return res

   ··· 喜欢今天的题, 非常好

[wtdcai]

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

[testplm]

class Solution:
    def new21Game(self, n, k, maxPts):
        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
        for i in range(k - 1, -1, -1):
            for j in range(1, maxPts + 1):
                dp[i] += dp[i + j] / maxPts
        return dp[0]

• Time:O(min(n,k+maxPts))
• Space:O(k+maxPts)

[snmyj]

class Solution {
    private double total=0;
    private double below=0.0;
    public double new21Game(int N, int K, int W) {

        count(0 , N, K, W);
        return below/total;
    }
    public void count(int temp , int N , int K , int W){
        if(temp>=K){
            total++;
            if(temp<=N){
                below++;
            }
            return;
        }else{
            for(int i=1 ; i<=W ; i++){
                count(temp+i , N , K , W);
            }
        }
    }
}

[ringo1597]

代码

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];
    }
}

[chenming-cao]

解题思路

动态规划+滑动窗口。参考官方题解 如果用dp[i]表示当前分数为i的情况下，爱丽丝的分数不超过n的概率，则dp[i] = (dp[i + 1] + dp[i + 2] + ... + dp[i + maxPts]) / maxPts，这就是动态转移方程，从后往前遍历。 每次求sum过程中仅变化左右两侧的数，中间维持不变，用滑动窗口降低时间复杂度。

代码

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        if (k == 0 || n >= k + maxPts) return 1;
        double dp[] = new double[n + 1];
        double wsum = 1, res = 0;
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i] = wsum / maxPts;
            if (i < k) wsum += dp[i];
            else res += dp[i];

            if (i - maxPts >= 0) wsum -= dp[i - maxPts];
        }
        return res;
    }
}

复杂度分析

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

[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]
}

Time: O(n)

[yuexi001]

思路

dp

思路

C++ 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];
    }
};

复杂度分析

• 时间复杂度：$O(min(n,k+maxPts))$
• 空间复杂度：$O(k+\textit{maxPts})$

[Elsa-zhang]

''' 21点
    爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。 每次抽取都是独立的，其结果具有相同的概率。
    当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？
    # 思路: 动态规划+滑动窗口
'''

class Solution:
    def new21Game(self, n: int, k: int, W: int):
        # 超时
        # dp = [0] * (k + W)

        # # 初始化 dp[i] 依赖 dp[i + x]，其中 x 属于 [1,W]
        # for i in range(k, k + W):
        #     if i <= n:
        #         dp[i] = 1

        # # dp[i]表示当前分数为 i 的情况下，分数不超过 N 的概率
        # 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]

        dp = [0] * (k + W)
        window_sum = 0
        # 初始化 dp[i] 依赖 dp[i + x]，其中 x 属于 [1,W]
        for i in range(k, k + W):
            if i <= n:
                dp[i] = 1
            window_sum += dp[i]

        # dp[i]表示当前分数为 i 的情况下，分数不超过 N 的概率
        for i in range(k-1, -1, -1):
            dp[i] = window_sum / W
            window_sum += dp[i] - dp[i+W]
        return dp[0]

n = 21
k = 17
W = 10

solution = Solution()
ans = solution.new21Game(n,k,W)
print(ans)

[heng518]

class Solution { public: double new21Game(int n, int k, int maxPts) { if(k == 0 || n >= k + maxPts) { return 1.0; }

    double res = 0.0;
    double sum = 0.0;
    vector<double> vec(n + 1);

    for (int i = 1; i <= n; i++) {
        vec[i] = i <= maxPts ? sum / maxPts + 1.0 / maxPts : sum/maxPts;
        if (i >= k) {
            res += vec[i];
        }
        else if (i < k) {
            sum += vec[i];
        }

        if (i > maxPts) {
            sum -= vec[i - maxPts];
        }
    }
    return res;
}

};

[Abby-xu]

思路

sliding window + DP

代码

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]

复杂度

O(n)/O(n)

[mayloveless]

思路

参考官解，核心dp，用滑动窗口优化循环过程

代码

var new21Game = function(n, k, maxPts) {
    if (k == 0) {
        return 1;
    }
    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 += dp[i];
    }

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

复杂度

时间：O(wk） 空间：O(w+k) w为maxPts

[A-pricity]

/**
 * @param {number} n
 * @param {number} k
 * @param {number} maxPts
 * @return {number}
 */
var new21Game = function(N, K, W) {
    let dp = new Array(N+1).fill(0);
    let sumArr = new Array(N+1).fill(0);
    dp[0]=1;
    for(let n=1;n<=N;n++){
        let left = Math.max(0,n-W);
        let right = Math.min(n-1,K-1);
        let p=0
        for(let i=left;i<=right;i++){
            p+=dp[i]/W;
        }
        dp[n]=p;
        sumArr[n]=sumArr[n-1]+p;
    }
    let result = 0;
    for(let i=K;i<=N;i++){
        result+=dp[i]
    }
    return result;
};

[zywang0]

class Solution {
    private double total=0;
    private double below=0.0;
    public double new21Game(int N, int K, int W) {

        count(0 , N, K, W);
        return below/total;
    }
    public void count(int temp , int N , int K , int W){
        if(temp>=K){
            total++;
            if(temp<=N){
                below++;
            }
            return;
        }else{
            for(int i=1 ; i<=W ; i++){
                count(temp+i , N , K , W);
            }
        }
    }
}

[zhiyuanpeng]

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

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

[bookyue]

code

    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];
    }

[Alyenor]

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

};

[liuajingliu]

var new21Game = function(N, K, W) { if(K>N) return 0 const dp = new Array(K+W).fill(1) let temp = K let s = 0 while(temp<K+W){ if(temp>N){ dp[temp] = 0 } s+=dp[temp] temp++ } let downTemp = K-1 while(downTemp>=0){ dp[downTemp] = s/W s = s+dp[downTemp]-dp[downTemp+W] downTemp-- } return dp[0] };

[whoam-challenge]

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 for i in range(k - 1, -1, -1): for j in range(1, maxPts + 1): dp[i] += dp[i + j] / maxPts return dp[0]

[AtaraxyAdong]

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];
    }
}

[Moin-Jer]

class Solution { private double total=0; private double below=0.0; public double new21Game(int N, int K, int W) {

    count(0 , N, K, W);
    return below/total;
}
public void count(int temp , int N , int K , int W){
    if(temp>=K){
        total++;
        if(temp<=N){
            below++;
        }
        return;
    }else{
        for(int i=1 ; i<=W ; i++){
            count(temp+i , N , K , W);
        }
    }
}

}

[tiandao043]

思路

看了题解dp+滑动窗口，维护中间滚动数组，从后往前填字，注意边界情况，n与k与maxpts的关系范围。

代码

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

O(min⁡(n,k+maxPts)) O(k+maxPts)

[buer1121]

    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]

[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;
        }
        for (int i = k - 1; i >= 0; i--) {
            for (int j = 1; j <= maxPts; j++) {
                dp[i] += dp[i + j] / maxPts;
            }
        }
        return dp[0];
    }
};

[klspta]

class Solution {
    public double new21Game(int N, int K, int maxPts) {
        if (K == 0) {
            return 1.0;
        }
        double dp [] = new double[20010];
        for (int i = K; i <= N; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i <= maxPts; i++){
            dp[K - 1] += dp[K - 1 + i] / maxPts;
        }
        for (int i = K - 2; i >= 0; i--){
            dp[i] = dp[i + 1] + (dp[i + 1] - dp[i + maxPts + 1]) / maxPts;
        }
        return dp[0];
    }
}

[paopaohua]

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;
    }
}

[xuanaxuan]

思路

类似爬楼梯

状态方程:dp[x]=1/w dp[x+1]+ 1/w dp[x+2] + 1/w dp[x+3]...+ 1/w dp[x+w]

先求出K-W之间的概率，再反推出dp[0]

代码

const new21Game = (N, K, W) => {
  const dp = new Array(K+W).fill(0);
  let s=0;
  for (let i = 0; i < W; i++) {
    const index=K+i
    dp[index]=index<=N?1 :0
    s+=dp[index]
  }
  for (let i = K-1; i >=0; i--) {
    dp[i]=s/W
   s=s-dp[i+W]+dp[i]
  }
  return dp[0]
};

复杂度

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

[darwintk]

根据动态转移方程

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
        for i in range(k - 1, -1, -1):
            for j in range(1, maxPts + 1):
                dp[i] += dp[i + j] / maxPts
        return dp[0]

[Jetery]

代码 (cpp)

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0)
            return 1.0;

        double d[k+maxPts];
        memset(d, 0, sizeof(d));
        for (int i = k; i <= n & i < k + maxPts; ++i)
            d[i] = 1.0;

        d[k-1] = 1.0*min(n-k+1, maxPts) / maxPts;
        for (int i = k - 2; i >= 0; --i)
            d[i] = d[i+1] - (d[i+maxPts+1]-d[i+1])/ maxPts;

        return d[0];
    }
};

复杂度分析

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

[neado]

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;
    }
}