azl397985856 commented 2 years ago

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

yetfan commented 2 years ago

思路 dp+滑动窗口我们计算她手里有不同得分的概率，逆推最初始还没得分的概率dp[0]。

1.从0到k-1的概率是需要计算的，当前分数x的获胜概率，是下一次抽卡w种可能性的平均值即是dp[x] = (dp[x+1] + dp[x+2]...+dp[x+w]) /w

2.从k开始以后，不可以再抽牌，概率直接根据和n比大小的结果，来判断。大于n，0%的可能性，小于等于n，100%的可能性

3.通过逆推dp[k-1]为后十个概率的平均值

dp[k-1] = (dp[k] + ... + dp[k+w-1] + dp[k+w]) / w dp[k-2] = (dp[k-1] + dp[k] + ... +dp[k+w-1] ) / w

好家伙中间这一串都一样啊因此，滑动窗口搞起来计算sum，每次加上前一个减去后一个，一直推出来dp[0]，解决战斗

代码

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

复杂度 时间 O(k+w) 空间 O(k+w)

laofuWF commented 2 years ago

# dp + sliding window

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

        dp = [0 for i in range(n + 1)]
        win = 1
        res = 0
        dp[0] = 1

        for i in range(1, n + 1):
            dp[i] = win / maxPts

            if i < k:
                win += dp[i]
            else:
                res += dp[i]

            if i - maxPts >= 0:
                win -= dp[i - maxPts]

        return res

zwmanman commented 2 years ago

class Solution(object): def new21Game(self, n, k, maxPts): """ :type n: int :type k: int :type maxPts: int :rtype: float """ dp = [0] * (k + maxPts)

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

    s = min(n - k + 1, maxPts)

    for i in range(k - 1, -1, -1):
        dp[i] = s/float(maxPts)
        s += dp[i] - dp[i + maxPts]

    return dp[0]

li65943930 commented 2 years ago

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

zhangzz2015 commented 2 years ago

关键点

首先思考该问题，通过top down方法，当我们当前的总分是curPts，我们可以从[1 maxPts]去抽牌，每个牌的概率为1/maxPts。很容易写出如下方法1，递归方法。继续可考虑有很多重复子问题。写出方法2，dfs + mem 。但是复杂度还是很高。
通过上面的top down 方法，我们可以写出递推关系 dp[x] = 1/ maxP * (dp[x+1] ...... dp[x+maxP])。根据该递推关系，我们可发现当前的状态和 maxP 状态相关。有两种转化方法。
方法3: dp(x) = 1/ maxP (dp[x+1] ...... dp[x+maxP]) dp(x+1) = 1/ maxP (dp[x+2] ...... dp[x+maxP+1]) dp(x) - dp(x+1) = 1/maxP *( dp[x+1] - dp[x+maxP+1])
方法4: 根据如上的递推关系，可发现为固定窗口 maxP 的滑动窗口。因此可使用滑动窗口的办法。
注意在通过方法3和方法4时候要处理 base情况

代码

语言支持：C++

C++ Code:

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {

        return dfs(n, k, maxPts, 0); 

    }

    double dfs(int n, int k, int maxPts, int curPts)
    { 
        if(curPts>=k)
        {
           if(curPts>n)
              return 0.;            
            else
              return 1.0; 
        }
        double ret =0; 
        for(int i=1; i<=maxPts; i++)
        {
             ret += dfs(n, k, maxPts, curPts + i)/ maxPts; 
        }        
        return ret;         
    }
};

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {

        vector<double> mem(k,-1); 
        return dfs(n, k, maxPts, 0, mem); 

    }      
    double dfs(int n, int k, int maxPts, int curPts, vector<double>& mem)
    { 
        if(curPts>=k)
        {
           if(curPts>n)
              return 0.;            
            else
              return 1.0; 
        }
        if(mem[curPts]>=0)
            return mem[curPts]; 
        double ret =0; 
        for(int i=1; i<=maxPts; i++)
        {
             ret += dfs(n, k, maxPts, curPts + i, mem)/ maxPts; 
        } 
        mem[curPts] = ret; 
        return ret;         
    }
};

```c++   dfs + mem  方法3 .
class Solution {
public:

///  F(x) = (F(x+1) + F(x+2) + ... + F(x+W)) / W
///  F(x+1) = (F(x+2) + F(x+3) + ... + F(x+1+W)) / W
///   After a substraction, we have

///  F(x) = F(x+1) - 1/W * (F(x+1+W) - F(x+1))    
    double new21Game(int n, int k, int maxPts) {
        if( k == 0 || n >= k + maxPts)
            return 1;        
        vector<double> mem(k,-1); 
        return dfs(n, k, maxPts, 0, mem); 

    }

    double dfs(int n, int k, int maxPts, int curPts, vector<double>& mem)
    {
        if (curPts == k-1)
            return min((double)(n-k+1), (double)maxPts) / maxPts; 
        if(curPts>=k)
        {
           if(curPts>n)
              return 0.;            
            else
              return 1.0; 
        }
        if(mem[curPts]>=0)
            return mem[curPts]; 
        double ret =0; 
/*        for(int i=1; i<=maxPts; i++)
        {
            if(curPts+i>n)
                break; 
             ret += dfs(n, k, maxPts, curPts + i, mem)/ maxPts; 
        } */
        ret =  dfs(n, k,  maxPts, curPts+1, mem) - 1.0/maxPts*(dfs(n, k, maxPts, curPts+1+maxPts, mem) 
                                                               -dfs(n, k, maxPts, curPts+1, mem)); 
        mem[curPts] = ret; 
        return ret;         
    }
};

 //  dp[x] =  1/ maxP * (dp[x+1] ......  dp[x+maxP])  
 //  dp[x-1] = 1/maxP* (dp[x] +......  dp[x+maxP-1])
    double new21Game(int n, int k, int maxPts) {

      int maxK = min(k-1, n); 
       vector<double> dp(maxK+1+maxPts, 0); 
      //  when x= k-1. we get card from 1 to maxpts. 
      //  let base case. from k to k+maxpts
      //  when n  
       double sum =0; 
       for(int i =maxK+1; i<maxK+1+maxPts; i++)
       {
           if(i>n) 
               dp[i] =0;
           else
               dp[i] =1; 
           sum += dp[i];            
       }
       for(int i=maxK; i>=0; i--)
       {
           dp[i] = sum/maxPts; 
           sum += dp[i]; 
           sum -= dp[i+maxPts]; 
       } 
        return dp[0]; 
    }        
};

feifan-bai commented 2 years ago

思路

滑动窗口 + DP 代码

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]

复杂度分析

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

MengyuZang commented 2 years ago

Idea

DP

Code:

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

Big-O

O(K + W)

YuyingLiu2021 commented 2 years ago

#solution 1
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 i in range(k-1,-1,-1):      
            dp[i]=s/maxPts
            s=s-dp[i+maxPts]+dp[i]

        return dp[0]

Solution 2:
class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp,s=[1],1

        for i in range(1,k+maxPts):
            dp.append(s/maxPts)
            if i+1>maxPts:s-=dp.pop(0)
            if i+1<=k:s+=dp[-1]

        return 1 if k==0 else sum(dp[:n-k+1])

zwx0641 commented 2 years ago

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

wangzehan123 commented 2 years ago

Java Code:


class Solution {
    public double new21Game(int N, int K, int W) {
        double[] DP=new double[K+W];
        if(K==0)
            return 1;
        DP[0]=1;
        DP[1]=1d/W;
        for(int a=2;a<=K+W-1;a++)
                DP[a]=(DP[a-1]*(W+(a>K?0:1))-(a-W-1>=0?DP[a-W-1]:0))/W;
        return Arrays.stream(DP).limit(N+1).skip(K).sum();
    }
}

cszys888 commented 2 years ago

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

        s = sum(dp[k:(k+maxPts)])/maxPts
        if k>=1:
            dp[k - 1] = s

        if k>=2:
            for i in range(k-2,-1,-1):
                s = s + (dp[i+1] - dp[i+1+maxPts])/maxPts
                dp[i] = s

        return dp[0]

time complexity : O(k+MaxPts) space complexity: O(k+MaxPts)

rzhao010 commented 2 years ago

Thoughts DP, really hard to get the state transition equation straight. Sad~

Code

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

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

yan0327 commented 2 years ago

思路: 动态规划+滑动窗口优化

func new21Game(n int, k int, maxPts int) float64 {
    if k == 0{
        return 1.0
    }
    dp := make([]float64,maxPts+k)
    win := 0.0
    for i:=k;i<=n&&i<k+maxPts;i++{//从后往前DP，从可能的答案结果往前推
        dp[i] = 1.0
        win += dp[i]
    }
    for i:=k-1;i>=0;i--{//从最后一次答案往前推
        dp[i] = win/float64(maxPts)
        win += dp[i]-dp[i+maxPts]
    }
    return dp[0]
}

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

baddate commented 2 years ago

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

Tesla-1i commented 2 years ago

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]

shamworld commented 2 years ago

var new21Game = function(N, K, W) {
    if(K===0)return 1;
    if(K===1)return Math.min(N,W)/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=(sumArr[right]-sumArr[left]+dp[left])/W
        dp[n]=p;
        sumArr[n]=sumArr[n-1]+p;
    }
    return sumArr[N]-sumArr[K-1];
};

hdyhdy commented 2 years ago

思路：动态规划 + 滑动窗口 func new21Game(n int, k int, maxPts int) float64 { dp := make([]float64, k + maxPts) var num float64

for i := k ;i <= k - 1 + maxPts ;i ++ {
    if i <= n {
        dp[i] = 1
    }else {
        dp[i] = 0
    }
    num += dp[i]
}

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

} 时间复杂度：O（k + maxpts）空间复杂度：O（k + maxpts）

ginnydyy commented 2 years ago

Problem

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

Notes

DP + sliding window (reference: https://leetcode-cn.com/problems/new-21-game/solution/xin-21dian-by-leetcode-solution/)
To get the DP formula, use double[] dp, dp[i] is the probability to win when starting from i points, the answer of the problem is dp[0].
The problem is converted to how to find the value of dp[0].
when 0 <= i < k - 1, (dp[i] = dp[i + 1] + dp[i + 2] + ... + dp[i + maxPts]) / maxPts
When i == k - 1, which is the max points before the last time of drawing cards, the probability to win is the sum of the probability of drawing a card that k - 1 + pts <= n. So dp[k - 1] == sum(the probability to win when next time drawing a card with (1, 2, ... n - k + 1) pts).
But maxPts may be smaller than n - k + 1, so next drawing cards with pts less than min(n - k + 1, maxPts) will count as win. So dp[k - 1] == sum(the probability to win when next time drawing a card with (1, 2, ... min(n - k + 1, maxPts)) pts).
- When i == k - 1 and draw a card with 1 pts next time, the total points is k - 1 + 1. The probability to win is the probability to win when starting from k - 1 + 1 pts, ==> k pts.
- When i == k - 1 and draw a card with 2 pts next time, the total points is k - 1 + 2. The probability to win is the probability to win when starting from k - 1 + 2 pts, ==> k + 1 pts.
- ...
- When i == k - 1 and draw a card with min(n - k + 1, maxPts) pts next time, the total points is k - 1 + min(n - k + 1, maxPts). The probability to win is the probability to win when starting from k - 1 + min(n - k + 1, maxPts) pts, ==> min(n, k - 1 + maxPts).
- So the probability to win when starting from k - 1 pts, is sum(dp[k] + dp[k + 1] + ... + dp[min(n, k - 1 + maxPts)]) / maxPts. / maxPts here because when having k - 1 point, the probability to draw any card is 1 / maxPts.
When i >= k, the game is starting with k or more pts, there is no next draw, and k is guaranteed to be smaller than n, so the probability to win is 100%, 1.0d. So when i is in [k, min(n, k - 1 + maxPts)] range, dp[i] is 1.0.
- Thus dp[k - 1] = sum(dp[k] + dp[k + 1] + ... + dp[min(n, k - 1 + maxPts)]) / maxPts = 1.0 (min(n, k - 1 + maxPts) - k + 1) / maxPts = 1.0 min(n - k + 1, maxPts) / maxPts.
So we know:
- when 0 <= i < k - 1, dp[i] = dp[i + 1] + dp[i + 2] + ... + dp[i + maxPts]) / maxPts
- When i == k - 1, dp[i] = 1.0 * min(n - k + 1, maxPts) / maxPts
- When k <= i <= min(n - k + 1, maxPts), dp[i] = 1.0
- when k > min(n - k + 1, maxPts), dp[1] = 0.0 (can ignore)
So we can descendingly calculate dp[0].
For dp[i] = dp[i + 1] + dp[i + 2] + ... + dp[i + maxPts]) / maxPts, we need to use embedded for loop to get the sum in the inner loop, and accumulate it in the outer loop. Outer loop iterates k times, inner loop iterates maxPts, total O(k maxPts). k <= 10^4, maxPts <= 10^4, so O(k maxPts) = 10^8, greater than 10^7, will cause TLE.
To optimize time complexity, comparing the diff between dp[i] and dp[i + 1], we can get dp[i] = dp[i + 1] - (dp[i + 1 + maxPts] - dp[i + 1]) / m, equally to use a sliding window to add one new item and remove one old item for each single loop, to avoid embedded loop.
So we know:
- when 0 <= i < k - 1, dp[i] = dp[i + 1] - (dp[i + 1 + maxPts] - dp[i + 1]) / m
- When i == k - 1, dp[i] = 1.0 * min(n - k + 1, maxPts) / maxPts
- When k <= i <= min(n - k + 1, maxPts), dp[i] = 1.0
- when k > min(n - k + 1, maxPts), dp[1] = 0.0 (can ignore)

Solution

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

        double[] dp = new double[k + maxPts];

        // when x in [k, min(n, k - 1 + maxPts)], dp(x) == 1.0
        for(int i = k; i <= n && i <= k + maxPts - 1; i++){ // although the lenght of dp[] is k + maxPts, actual valid number of elements is min(n, k - 1 + maxPts), others are 0.0, means always lose.
            dp[i] = 1.0;
        }

        // when x == k - 1, dp(x) == min(n - k + 1, maxPts) / maxPts
        dp[k - 1] = 1.0 * Math.min(n - k + 1, maxPts) / maxPts;

        // when x in [0, k - 1), dp(x) = dp(x + 1) - (dp(x + 1 + maxPts) - dp(x + 1)) / maxPts
        for(int i = k - 2; i >= 0; i--){
            dp[i] = dp[i + 1] - (dp[i + 1 + maxPts] - dp[i + 1]) / maxPts;
        }

        return dp[0];
    }
}

Complexity

Time: O(min(n, k + maxPts)) for the total iteration times of two separate for loops.
Space: O(k + maxPts) for the double[] dp array.

Joyce94 commented 2 years ago

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]

wenlong201807 commented 2 years ago

代码块


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

时间复杂度和空间复杂度

时间复杂度 O(n)
空间复杂度 O(1)

ivangin commented 2 years ago

code

  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], sum = 1, res = 0;
      dp[0] = 1;
      for (int i = 1; i <= N; ++i) {
        dp[i] = sum / W;
        if (i < K) sum += dp[i]; else res += dp[i];
        if (i - W >= 0) sum -= dp[i - W];
      }
      return res;
    }
  }

chengyufeng6 commented 2 years ago

double new21Game(int N, int K, int W){ if (K == 0 || N == 0) { return 1.0; } double dp = (double)malloc(sizeof(double) (N + 1)); memset(dp, 0.0, sizeof(double) (N + 1)); dp[0] = 1.0; int i; double res = 0.0; double sum = 1;

for (i = 1; i <= N; i++) {
    dp[i] = sum / W;
    if (i < K) { 
        sum += dp[i];
    }
    if (i >= W) { 
        sum -= dp[i - W];
    }
    res += (i >= K) ? dp[i] : 0.0;
}
free(dp);
return res;

}

xuhzyy commented 2 years ago

思路

动态规划

代码

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

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)

kbfx1234 commented 2 years ago

837. 新 21 点

// 1-24
/* 
dp[i]: 当前分数为i的情况下，分数不超过N的概率
dp[i] = sum(dp[i+x] for x in range(1, W+1)) / W
dp[i] = (dp[i+1]+dp[i+2]+···+dp[i+W]) / W
dp[i-1] = (dp[i]+dp[i+1]+···+dp[i+W-1]) / W = dp[i] + (dp[i] - dp[i+W]) / W
*/

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+1] - dp[i+maxPts+1]) / maxPts;
        }   
        return dp[0];
    }
};

iambigchen commented 2 years ago

代码

语言支持：JavaScript

JavaScript Code:


/**
 * @param {number} n
 * @param {number} k
 * @param {number} maxPts
 * @return {number}
 */
 var new21Game = function (n, k, maxPts) {
    const dp = new Array(k + maxPts + 2).fill(0);

    let windowSum = 0;
    for (let i = k; i < k + maxPts; i++) {
      if (i <= n) dp[i] = 1;
      windowSum += dp[i];
    }

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

    return dp[0];
};

复杂度分析

令 n 为数组长度。

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

tongxw commented 2 years ago

思路

这个题的难点在于理解题意。。另外似乎是唯一一个dp从后向前推的动规。

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

        for (int i = k - 1; i >= 0; i--) {
            dp[i] = sum / maxPts;
            sum += dp[i] - dp[i+maxPts]; // 滑动窗口计算长度为maxPts的和
        }

        return dp[0];
    }
}

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

haixiaolu commented 2 years ago

代码

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp = [0] * (k + maxPts)

        total_point = 0
        for i in range(k, k + maxPts):
            if i <= n:
                dp[i] = 1
            total_point += dp[i]

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

tangjy149 commented 2 years ago

代码

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

dahaiyidi commented 2 years ago

Problem

837. 新 21 点

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：

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

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

爱丽丝的分数不超过 n 的概率是多少？

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

Note

首先理解题目是一个难点。当i< k，还能抽，当i>=k，游戏停止，判断值是否<n.
i 的取值范围是[0, k - 1 + maxPts],最终需要返回的是dp[0]
动态规划：dp[i]= 1/maxPts * (dp[i + 0] + ... + dp[i + maxPts]),在计算累加结果时，可以运用滑动窗口
当i>=k时，dp[i]是确定的，概率为int(i <= n)

Complexity

时间O：K+W
空间O：K+W

Python

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        # i 的取值范围是[0, k - 1 + maxPts],最终需要返回的是dp[0]
        # 动态规划：dp[i]= 1/maxPts * (dp[i + 0] + ... + dp[i + maxPts]),在计算累加结果时，可以运用滑动窗口
        # 当i>=k时，dp[i]是确定的，概率为int(i <= n)

        dp = [0] *  (k + maxPts)
        s = 0
        for i in range(k, len(dp)):
            dp[i] = int(i <= n)
            s += dp[i]
        for i in range(k - 1, -1, -1):
            dp[i] = 1 / maxPts * s
            s += (dp[i] - dp[i + maxPts])
        return dp[0]

C++

From : https://github.com/dahaiyidi/awsome-leetcode

RocJeMaintiendrai commented 2 years ago

class Solution {
    public double new21Game(int n, int k, int w) {
        if(n >= k + w - 1) return 1.0;
        if(n < k) return 0.0;
        if(k == 0) return 1.0;
        double[] dp = new double[k + w];
        double prob = (double)(1) / (double)(w);
        dp[0] = 1.0;
        double sum = 1.0;
        for(int i = 1; i < k + w; i++) {
            dp[i] = prob * sum;
            if(i < k) sum += dp[i];
            if(i - w >= 0) sum -= dp[i - w];
        }
        double res = 0.0;
        for(int i = k; i <= n; i++) {
            res += dp[i];
        }
        return res;
    }
}

复杂度分析

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

WANGDI-1291 commented 2 years ago

代码

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]

时间复杂度：O（K+N）
空间复杂度：O（K+N）

LuoXingbiao commented 2 years ago

思路

动态规划加滑动窗口，先贴代码，之后再重做一遍。

代码

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]

复杂度分析

时间复杂度:O(k + w)

空间复杂度:O(k + w)

LannyX commented 2 years ago

思路

DP

代码

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        double[] dp = new double[k + maxPts];
        double s = 0;
        for(int i = k; i < k + maxPts; i++){
            if(i <= n){
                dp[i] = 1;
            }
            else{
                dp[i] = 0;
            }
            s += dp[i];
        }

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

复杂度分析

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

ZJP1483469269 commented 2 years ago

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.0 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]

falconruo commented 2 years ago

思路: 动态规划 + 滑动窗口

复杂度分析:

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

代码(C++):

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0) return 1.0;
        vector<double> dp(k + maxPts + 1, 0);

        double winSum = 0;
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
            winSum += dp[i];
        }

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

        return dp[0];
    }
};

CoreJa commented 2 years ago

思路

回溯：写起来简单，纯模拟，复杂度爆炸，TLE (用例86 / 151)
回溯+记忆化：用二维数组(数组+哈希)储存入参的结果，复杂度仍然爆炸，TLE(用例90 / 151)
动规：dp[i]表示当前点数为i时，达到条件的概率。maxPts为每次可以取的点数，那么状态方程显然有：$dp[i]=sum(dp[i+1:i+maxPts+1])/maxPts$。即dp[i]是它后面maxPts个dp的平均值。以maxPts=10，k=17，n=21为例，显然$dp[17]\dots dp[21]$均为1，$dp[22]\dots dp[26]$均为0，dp[16]即为当点数为16时，随机抽$[1,10]$使结果小于等于21的概率，答案即为$(\sum^{10}_{i=1}dp[16+i])/10$，复杂度$O(k*maxPts)$，TLE (用例102 / 151)
动规+滑动窗口：求和不需要重复计算，每次都只用滑动一位，复杂度$O(k+maxPts)$

代码

class Solution:
    # 回溯：写起来简单，纯模拟，复杂度爆炸，TLE (用例**86 / 151**)
    def new21Game1(self, n: int, k: int, maxPts: int) -> float:
        ans = 0

        def dfs(cur, p):
            nonlocal ans
            if cur >= k:
                if cur <= n:
                    ans += p
                return
            for i in range(1, maxPts + 1):
                dfs(cur + i, p * 1 / maxPts)

        dfs(0, 1)
        return ans

    # 回溯+记忆化：用二维数组(数组+哈希)储存入参的结果，复杂度仍然爆炸，TLE(用例**90 / 151**)
    def new21Game2(self, n: int, k: int, maxPts: int) -> float:
        dp = [{} for _ in range(k + maxPts)]

        def dfs(cur, p):
            if cur >= k:
                if cur <= n:
                    return (1 / maxPts) ** p
                return 0
            if p in dp[cur]:
                return dp[cur][p]
            ans = 0
            for i in range(1, maxPts + 1):
                ans += dfs(cur + i, p + 1)
            dp[cur][p] = ans
            return ans

        x = dfs(0, 0)
        return x

    # 动规：`dp[i]`表示当前点数为`i`时，达到条件的概率。maxPts为每次可以取的点数，那么状态方程显然有：
    # $dp[i]=sum(dp[i+1:i+maxPts+1])/maxPts$。即`dp[i]`是它后面`maxPts`个dp的平均值。以`maxPts=10`，
    # `k=17`，`n=21`为例，显然$dp[17]\dots dp[21]$均为1，$dp[22]\dots dp[26]$均为0，`dp[16]`即为当点数
    # 为16时，随机抽$[1,10]$使结果小于等于21的概率，答案即为$(\sum^{10}_{i=1}dp[16+i])/10$，
    # 复杂度$O(k*maxPts)$，TLE (用例**102 / 151**)
    def new21Game3(self, n: int, k: int, maxPts: int) -> float:
        dp = [0] * k + [1] * (n - k + 1) + [0] * (k + maxPts - n - 1)
        for i in range(k - 1, -1, -1):
            dp[i] = sum(dp[i + 1:i + maxPts + 1]) / maxPts
        return dp[0]

    # 动规+滑动窗口：求和不需要重复计算，每次都只用滑动一位，复杂度$O(k+maxPts)$
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp = [0] * k + [1] * (n - k + 1) + [0] * (k + maxPts - n - 1)
        window = sum(dp[-maxPts:])
        dp[k - 1] = window / maxPts
        for i in range(k - 2, -1, -1):
            window += dp[i + 1] - dp[i + 1 + maxPts]
            dp[i] = window / maxPts
        return dp[0]

JudyZhou95 commented 2 years ago

Solution

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

        dp = [1] + [0] * n
        window_sum = 1 
        for i in range(1, n+1):
            dp[i] = window_sum/maxPts
            if i < k: window_sum += dp[i]
            if i - maxPts >= 0: window_sum -= dp[i-maxPts]

        return sum(dp[k:])

Analysis

dp[i] is the probability that we can get i at some moment during this game. dp[i] = sum_all_the_m(dp[i-m] x p(we get an m next draw)). All the possible m values are from 1 to the maxPts, and the probability od getting each one is 1/maxPts. Therefore dp[i] = (1/maxPts) * sum(last maxPts terms of dp). we can maintain a sliding window with size at most maxPts to keep track of the sum in the equation. \ Time Complexity: O(N)\ Space Complexity: O(N)

tian-pengfei commented 2 years ago

class Solution {
public:
//    不超过n的概率 ，当超过k时立即停止， [1,maxPts] 牌的范围
    double new21Game(int n, int k, int maxPts) {
         if(n==0||k==0) return 1;
//        f(x)为手中牌的值为x时，在[k,n]之间的概率
        int f_size = min(k-1+maxPts,n)+1;
        vector<double> f(f_size,1);
        double p1 =  (double)1/maxPts;
        double  p_sum = f_size-k;
        f[k-1] = p_sum*p1;
        for (int i = k-2; i >=0 ; --i) {
            if(i+maxPts>=n){
                p_sum+=f[i+1];
            } else{
                p_sum+=f[i+1];
                p_sum-=f[i+maxPts+1];
            }
            f[i] = p_sum*p1;
        }
        return f[0];

    }

};

machuangmr commented 2 years ago

代码

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

zhiyuanpeng commented 2 years ago

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]

Yachen-Guo commented 2 years ago

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

KennethAlgol commented 2 years ago

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

        return dp[0];
    }
}

luhnn120 commented 2 years ago

思路

dp + 滑动窗口

代码

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

复杂度

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

chen445 commented 2 years ago

代码

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

Myleswork commented 2 years ago

思路

不能正确显示公式，可以复制到typora看看公式

今天这题还是蛮有趣的，通过全概率公式推出转移方程，再用滑动滑动窗口优化

转移方程：

注：$$m=maxPts$$ $$ dp[i]=\sum{c=1}^mdp[i+c]/m $$ 当然如何推导出这个方程才是最关键的，其实是用了概统里的全概率公式 $$ P(B)=\sum{c=1}^mP(A_i)P(B|A_i) $$ 全概率公式是什么我就不细讲了，可以参考各种教材。

显然我们可以设$$B$$为“抽取一个数后赢得比赛的概率”；而 $$ A_i $$ 为抽取的数，$$i$$为1~m

而根据dp思想，$$P(B|A_i)$$我们是知道的，$$P(A_i)$$均等于$$1/m$$

将$$P(B|A_i)$$转化为代码就是

for(c=1->m) sum(dp[i+c])

那dp初始怎么设置呢？当当前分数$$x>=k$$时，游戏结束，获胜条件为$$x<=n$$；这句话中我们可以看出游戏结束时所有分数中最小的一定是k，那最大的是什么呢？再进行最后一次选数是，最大的可以继续选数的分数是$$k-1$$，如果我们选到$$m$$，那就可以达到所有分数的最大值，即$$k-1+m$$，那也就是说，$$[k,k-1+m]$$这些分数是最后的分数，而其中小于等于n的分数赢得游戏，大于n的分数输了游戏。如果$$n\ge k-1+m$$，说明所有大于k的分数都小于n，那么这些分数就都赢了，对应dp全部设为1；反之则小于等于n的分数对应dp设为1，大于n的分数对应dp设为0；

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if(k == 0) return 1.0;  //k<=n
        vector<double> dp(k+maxPts);  //0~k-1+maxpts  最后返回dp[0]
        //初始化
        for(int i = k;i<=min(n,k-1+maxPts);i++) dp[i] = 1.0; //游戏赢了
        for(int i = k-1;i>=0;i--){
            for(int c = 1;c<=maxPts;c++) dp[i] += dp[i+c]/maxPts;  //全概率公式
        }
        return dp[0];
    }
};

很遗憾，TLE了，说明两层for不行，那仔细一想，每一次往0靠近的过程中，其实求和的个数并没有变，都是m个，变得只有头和尾，那么非常自然地，就可以用滑动串口进行优化

代码

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if(k == 0) return 1.0;  //k<=n
        vector<double> dp(k+maxPts);  //0~k-1+maxpts  最后返回dp[0]
        //初始化
        for(int i = k;i<=min(n,k-1+maxPts);i++) dp[i] = 1.0; //游戏赢了
        for(int c = 1;c<=maxPts;c++) dp[k-1] += dp[k-1+c]/maxPts;  //全概率公式
        for(int i = k-2;i>=0;i--){
            dp[i] = (dp[i+1]*maxPts+dp[i+1]-dp[i+1+maxPts])/maxPts;
        }
        return dp[0];
    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

stackvoid commented 2 years ago

思路

DP

代码

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

复杂度分析

O(N) O(N)

Serena9 commented 2 years ago

代码

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]

junbuer commented 2 years ago

思路

逆向动态规划

代码

class Solution(object):
def new21Game(self, n, k, maxPts):
    """
    :type n: int
    :type k: int
    :type maxPts: int
    :rtype: 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, k + maxPts))$
空间复杂度：$O(k+maxPts)$

harperz24 commented 2 years ago

class Solution {
    public int maxVowels(String s, int k) {

        int count = 0;

        for (int i = 0; i < k; i ++) {
            count += isVowel(s.charAt(i));
        }

        int res = count;

        for (int i = k; i < s.length(); i ++) {
            count = count + isVowel(s.charAt(i)) - isVowel(s.charAt(i - k));
            res = Math.max(res, count);
        }
        return res;
    }  

    public int isVowel(char n) {
        return (n == 'a' || n == 'e' || n == 'i' || n == 'o' || n == 'u')? 1:0;
    }
}

biaohuazhou commented 2 years ago

思路

CV

代码

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

复杂度分析 时间复杂度：$O(K+W)$ 空间复杂度：$O(K+W)$

leetcode-pp / 91alg-6-daily-check

【Day 44 】2022-01-24 - 837. 新 21 点 #54

837. 新 21 点

入选理由

题目地址

前置知识

题目描述

关键点

代码

Idea

Code:

Big-O

Problem

Notes

Solution

Complexity

代码块

时间复杂度和空间复杂度

思路

代码

837. 新 21 点

代码

思路

代码

代码

Problem

837. 新 21 点

Note

Complexity

Python

C++

代码

思路

代码

思路

代码

Solution

Analysis

代码

思路

代码

复杂度

代码

思路

代码

思路

代码

复杂度分析

代码

思路

代码

复杂度分析

思路

代码