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

wangzehan123 commented 3 years ago


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

复杂度分析

令 n 为数组长度。

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

yanglr commented 3 years ago

思路:

需要用动态规划来做, 然后可以用滑动窗口来优化。

如何使用动态规划来考虑本题?

假如 w=4, 那么每一轮随机得到的值的区间是[1, W], 即 [1,2,3,4],

dp数组: dp[i]: 中间路过分数 i 的概率. 看作一条路径, 在这条路径上能不能到达某个分数 i。

dp[i]之前的与之有关的状态有:

dp[i-4]
dp[i-3]
dp[i-2]
dp[i-1]

dp[i-1] -> dp[i-W] 范围内的有效状态, 满足:

i - W >= 0
且 i - W < k

w=4时, 如何计算dp[8]?

反推:

8 = 1+7=2+6=3+5=4+4

故 dp[8] = 1/4 dp[1] + 1/4 dp[2] + 1/4 dp[3] + 1/4 dp[4]

方法: 动态规划 + 滑动窗口优化

代码:

实现语言: C++

class Solution {
public:
    double new21Game(int N, int k, int W) {
        double dp[20005] = {0};
        double p = 1.0 / W;
        double sum = 0;
        dp[0] = 1;
        int l = 0, r = -1;
        for (int i = 0; i <= k - 1 + W; i++)
        {
            dp[i] += p * sum;
            if (i < k)
                sum += dp[i];
            r = i;
            while (r - l + 1 > W)
                sum -= dp[l++];
        }

        double res = 0;
        for (int i = k; i <= N; i++)
            res += dp[i];
        return res;
    }
};

复杂度分析

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

Daniel-Zheng commented 3 years ago

思路

动态规划。

代码(C++)

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 = 0; 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(K + W)
空间复杂度：O(K + W)

JiangyanLiNEU commented 3 years ago

DP+ sliding window (I checked the solution)

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

st2yang commented 3 years ago

思路

dp + 滑动窗口

代码

python


# dp[i] = (dp[i+1] + dp[i+2] + ... + dp[i+W]) / W

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)

fzzfgbw commented 3 years ago

思路

动态规划：最终落在k到n直接为赢，胜利概率为1，大于n为输，概率为0。因为抽卡概率均等，所以k-1时抽卡胜利的概率以k-1为起点，maxPts为步长的概率和除以maxPts，向前递推直至0起点

代码

func new21Game(n int, k int, maxPts int) float64 {
    dp := make([]float64,k + maxPts)
    sum:=0.0
    for  i := k;i<k+maxPts;i++  {
        if i<=n {
            dp[i] = 1.0
            sum+=dp[i]
        }else {
            break
        }
    }

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

复杂度分析

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

RocJeMaintiendrai commented 3 years ago

题目

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

思路

DP, 状态转移公式dp[i] = 1/w * (dp[i - 1] + ... + dp[i - w])

代码

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;
        //dp[i] = 1/w * (dp[i - 1] + ... + dp[i - w])
        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(k + w)

空间复杂度

O(k + w)

yachtcoder commented 3 years ago

dp + sliding window.

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

nonevsnull commented 3 years ago

思路

拿到题的直觉解法
- 完全没思路，只能从答案来理解解题过程。
- DP太差，需加强。

Nothing

从最简单的情形开始逐个推导dp公式这部分就是类似于climb stairs的逻辑。每个p都是确定走到当前位置的概率。因为最长步幅有W，因此一直从当前位置往前倒数的W个位置，都可以一步跨到当前位置，属于同等情况，需要做加法。
```
p0: 1
p1: p0 * 1/w
p2: p1 * 1/w + p0 * 1/w 
p3: p2 * 1/w + p1 * 1/w + p0 * 1/w
```
既然如此，我们其实可以求出来任意i位置的概率，就是上面公式的累加即可。
需要注意的一点是，我们要用到固定滑动窗口，来控制步幅，不在窗口范围的，即不在一步可跨越的范围，就不应该加起来，而应该去掉。
所以整个题目的结构，是以滑动窗口为模版的，类似于固定窗口左边缩进。每次都将当前位置的dp加入，一旦发现当前超过了步幅范围，就把最左指针的贡献去掉。
在这个基础上，最终的结果概率，使用的其实就是一个累积概率，一旦i超过或等于K了，就把每个当前位置的概率加总，得到的概率即为能走到:从K开始直到N，这些位置的概率的和

AC

代码

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

复杂度

time: O(N) space: O(N)

xj-yan commented 3 years ago

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        if (n >= k + maxPts - 1) return 1.0;

        double prob = 1.0 / maxPts, prev = 0;
        double[] prbArray = new double[k + maxPts];
        prbArray[0] = 1;

        for (int i = 1; i <= k; i++){
            prev = prev - (i - maxPts - 1 >= 0 ? prbArray[i - maxPts - 1] : 0) + prbArray[i - 1];
            prbArray[i] = prev * prob;
        }
        double res = prbArray[k];
        for (int i = k + 1; i <= n; i++){
            prev = prev - (i - maxPts - 1 >= 0 ? prbArray[i - maxPts - 1] : 0);
            prbArray[i] = prev * prob;
            res += prbArray[i];
        }
        return res;
    }
}

Time Complexity: O(n), Space Complexity: O(n)

pangjiadai commented 3 years ago

思路

DP + sliding window, 自己对DP没有思路，需要加强

Python3

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]

pophy commented 3 years ago

思路1 - DFS TLE

条件概率公式 p = p1 + p2 + p3... + pn

Java Code

    public double new21Game(int n, int k, int maxPts) {
        return dfs(n, k, maxPts, 0);
    }

    private double dfs(int n, int k, int maxPts, int currentTotal) {
        if (currentTotal >= k) {
            if (currentTotal <= n) {
                return 1D;
            }
            return 0;
        }
        double probability  = 0;
        for (int i = 1; i <= maxPts; i++) {
            probability += dfs(n, k, maxPts, currentTotal + i) * (1D / maxPts);
        }
        return probability ;
    }

时间&空间

时间 O(n^2)
空间 O(1)

思路2 - DP TLE

//dp[i] = (dp[i-1] + dp[i-2] + ... + dp[i-maxPts]) * 1/maxPts

Java Code

    public double new21Game(int n, int k, int maxPts) {
        double[] dp = new double[n + 1];
        dp[0] = 1D;
        for (int i = 1; i <= n; i++) {
            for (int j = i - maxPts; j <= i - 1; j++) {
                if (j < 0) {
                    continue;
                }
                if (j >= k) {
                    continue;
                }
                dp[i] += dp[j] * (1D / maxPts);
                System.out.println("i = " + i + " dp: " + dp[i]);
            }
        }
        double res = 0;
        for (int i = k; i <= n; i++) {
            res += dp[i];
        }
        return res;
    }

时间&空间

时间 O(n^2)
空间 O(n)

思路3 - DP + 滑动窗口

dp[i] = sum * (1/maxPts)
sum通过滑动窗口取值

Java Code

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

时间&空间

时间 O(n)
空间 O(n)

xieyj17 commented 3 years ago

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

        probs = [0] * (n+1)
        probs[0] = 1
        left, right = 0, 1
        total = sum(probs[left:right])
        for i in range(1, n+1):
            start = max(0, i - maxPts)
            end = min(k, i)
            total += sum(probs[right:end])
            total -= sum(probs[left:start])
            probs[i] += total / maxPts

            left, right = start, end

        return sum(probs[k:n+1])

My initial thought: Irwin–Hall distribution LOL

Time: O(nk)

Space: O(n)

ZacheryCao commented 3 years ago

Idea:

DP, sliding window. The possible points is [0, N]. Let dp[i] be the probablity to get i points. When we draw w from [1, W], the probablity to get i points after draw w is dp[i-w] / W. We can maintain a sliding window with size W. The sliding window's sum is the probability to get i-1 ~ i-W points. Everytime when we meet i - W >= 0 we need to increase the window's left side by 1. In other words we need to decrease the dp[i-W].

Code:

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

Complexity:

Time: O(N) Space; O(N)

zhy3213 commented 3 years ago

思路

dp，但朴素的dp超时，需要优化，于是再原有状态方程基础上优化差分，得到o(1)的计算时间

代码

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]

laofuWF commented 3 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

yingliucreates commented 3 years ago

link:

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

代码 Javascript

const new21Game = function (n, k, maxPts) {
  if (k + maxPts <= n || k === 0) return 1;

  let dp = [];
  dp[0] = 1;
  dp[1] = 1 / maxPts;

  for (let i = 2; i <= n; i++) {
    dp[i] = 0;

    if (i <= k) {
      dp[i] = (1 + 1 / maxPts) * dp[i - 1];
    } else {
      dp[i] = dp[i - 1];
    }
    if (i > maxPts) {
      dp[i] -= dp[i - maxPts - 1] / maxPts;
    }
  }

  return dp.reduce((acc, cur, idx) => {
    if (idx >= k) {
      acc += cur;
    }
    return acc;
  }, 0);
};

tongxw commented 3 years ago

思路

上期做完之后还是不太会。看了leetcode上有个题解讲的非常明白 Alice的得分情况，最多k + maxPts - 1，最少0分。其中当得分 >= k时，因为不能抽牌了，所以如果得分<=n胜率为1，>n胜率为0。之后从得分k-1开始填概率，因为此时可以抽到[1...maxPts]任意一张牌，概率为右侧maxPts个格子的概率和再除以maxPats 依次推到得分0的概率就是答案。 https://leetcode-cn.com/problems/new-21-game/solution/huan-you-bi-zhe-geng-jian-dan-de-ti-jie-ma-tian-ge/

代码

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 <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
            sum += dp[i];
        }

        for (int 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)

ghost commented 3 years ago

题目

New 21 Game

思路

Sliding window + DP 没看懂题看的答案思路

代码

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

        dp = [0] * (k + maxPts)
        curr_sum = 0

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

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

        return dp[0]

复杂度

Space: O(k+maxPts) Time: O(k+maxPts)

yan0327 commented 3 years ago

思路：对动态规划不是很熟，感觉是列状态方程再分析。我在研究一下

func new21Game(n int, k int, maxPts int) float64 {
    if k == 0{
        return 1.0
    }
    win_sum := 0.0
    dp := make([]float64, k+maxPts)
    for i:=k; i <= n&& i < k+maxPts; i++{
        dp[i] = 1.0
        win_sum += dp[i]
    }
    for i := k-1; i >= 0 ; i--{
        dp[i] = win_sum/float64(maxPts)
        win_sum += dp[i] - dp[i+maxPts]
    }
    return dp[0]
}

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

mannnn6 commented 3 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];
    }
}

复杂度

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

bingyingchu commented 3 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]
Time and Space: O(K+W)

laurallalala commented 3 years ago

代码

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

复杂度

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

thinkfurther commented 3 years ago

思路

在k+maxPts之前不可能出现溢出。那么就需要考虑k+maxPts之内的问题。如果最后一次在[k,n]之间，肯定不会溢出，设定为1。在k之前的每一次，转移到h后面maxPts个的概率是和除以maxPts。

代码

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+maxPts)

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

Moin-Jer commented 3 years ago

思路

求每种可能的不超过 N 的概率，超过 K 不能再改变，因此超过 K 的情况是否超过 N 是确定的，通过从后往前转移计算初始值为 0时不超过 N 的概率，结合滑动窗口优化区间求值

代码

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

复杂度分析

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

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

动态规划略显还是不够，保留滑动窗口结果不重复计算才是王道


class Solution:
def new21Game(self, n: int, k: int, maxPts: int) -> float:
#动态规划来做
#确定状态定义
#dp[i]表示当前分数为i时，分数不超过N的概率
#dp[i]=sum(dp[i+1]+......+dp[i+w])*1/w
#初始值，dp[i+1]......dp[i+w],分数小于N直接给1，因为大于k已经停止抽取
dp=[0]*(k+maxPts)
sum_value1=0
for i in range(k,k+maxPts):#当前已经小于等于N了，所以直接概率就是1
if i<=n:
dp[i]=1
sum_value1+=dp[i]
#滑动窗口才可以通过

    for i in range(k-1,-1,-1):
        if i==k-1:
            dp[i]=sum_value1/maxPts
        else:
            sum_value1=sum_value1+dp[i+1]-dp[i+maxPts+1]
            dp[i]=sum_value1/maxPts

    return dp[0]



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

zhangzhengNeu commented 3 years ago

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 <= n && i < k + maxPts; i++) { dp[i] = 1.0; sum += dp[i]; }

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

    return dp[0];
}

}

xjlgod commented 3 years ago

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

jiahui-z commented 3 years ago

Solution1

思路:

corner cases:
1. number drawing stops when accumulative points are bigger than k, then the theoretical maximum points Alice can get is k - 1 + maxPts (get k - 1 points then draw one more number, which can be as big as maxPts), if n is bigger than this, then it must happen
2. if k is zero, which means Alice can't draw anything at all, since the inital points are already at this level
formula maximum total points are k - 1 + maxPts, for each value in the interval [1, k - 1 + maxPts], the probability to reach it is the sum of probability to reach to total points i - pt, pt is the every number from [1, maxPts], times the independent probability which is 1 / maxPts
result explode in time due to high time complexity, cause TLE

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        // corner cass
        if (n >= k + maxPts || k == 0) return 1;

        double[] dp = new double[k+maxPts];
        dp[0] = 1;
        for (int i = 1; i < k + maxPts; i++) {
            for (int pt = 1; pt <= maxPts; pt++) {
                if (i - pt >= 0 && i - pt < k) {
                    dp[i] += dp[i-pt] / maxPts;
                }
            }
        }

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

Time complexity: O((k+maxPts) * maxPts) Space complexity: O(k+maxPts)

Solution2

思路:

corner cases: same as Solution1
formula basically the same as Solution1, but maintain sliding window with length as maxPts to avoid calculating the sum of probability for values in this window every time

class Solution {
    public double new21Game(int n, int k, int maxPts) {
       // corner cases
       if (n >= k + maxPts || k == 0) return 1;

       double[] dp = new double[n+1];
       dp[0] = 1;
       double pSum = 1, result = 0;
       for (int i = 1; i <= n; i++) {
           dp[i] = pSum / maxPts;
           if (i < k) {
               pSum += dp[i];
           } else {
               result += dp[i];
           }
           if (i - maxPts >= 0) {
               pSum -= dp[i - maxPts];
           }
       }
       return result;
    }
}

Time complexity: O(n) Space complexity: O(n)

kidexp commented 3 years ago

thoughts

参考的leetcode 官方题解用动态规划表示在i分的赢的概率

从k 到 min(n, k+maxPts) 因为都会赢，所以dp[i] = 1.0

从后往前推

dp[k-1] = (min(n, k + maxPts - 1) - k + 1) / maxPts 也就是从k到 min(n, k+maxPts) 之间的概率的和

剩下的0到k-2

dp[i] = sum(dp[i+1:i+maxPts+1])/maxPts

可以优化为，其实就是sliding window dp[i] = dp[i+1] - (dp[i+1+maxPts]-dp[i+1])/maxPts

code

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

complexity

Time O(k+maxPts)

Space O(k+maxPts)

Francis-xsc commented 3 years ago

思路

滑动窗口+动态规划

代码


class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        vector<double>dp(k+maxPts,0.0);
        double s=0;
        for(int i=k;i<k+maxPts;i++)
        {
            dp[i]= i<=n?1: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+maxPts)
空间复杂度：O(1)

zol013 commented 3 years ago

思路：这道题问的是最终得分sum 落在 k<= sum <= n 这个区间的概率是多少。创建动态规划array dp，让dp[i] 是在i这个数时赢的概率（赢就是说最终得分小于等于n）。先考虑base cases：如果累积的数是大于等于k的话就已经没有机会再抽牌了，所以概率是固定的。所以如果 k <= i <= n的话赢的概率一定为1。对于 k<= i <= n的i， dp[i] = 1. 再考虑i是小于k的情况，这个时候还可以继续抽牌，有1/maxPts的几率抽到1 到maxPts中任何数。所以再抽一次的话，总数将是在 i + 1, i + 2,......,i + maxPts中某一个，所以在i这个数时赢的可能性是在i+1, i+2,...,i+maxPts 赢的可能性的总和除以 maxPts (除以maxPts因为有 1/maxPts 几率抽到1 到maxPts中任何数) 所以 dp[i] = sum(dp[i + j] for j in range(1, maxPts)) / maxPts。我们反向dp，从 k -1 开始动态转移，因为直接动态规划的runtime是O(K* maxPts) 会TLE，我们维持一个sliding window sum, 因为从计算dp[i]到计算dp[i-1] 我们可以对sliding window sum 做出小修改：加入dp[i] 和减去dp[i+maxPts]. Python 3 code

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

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

        return dp[0]

Time Complexity: O(k + maxPts) Space Complexity: O(k + maxPts)

shibingchao123 commented 3 years ago

dp[i] = (dp[i+1] + dp[i+2] + ... + dp[i+W]) / W

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]

akxuan commented 3 years ago

最后没有过, 不过大概思路是对的.

找到状态转移方程. 就是找到从状态 i 到状态 i-1 的方程是什么. 已 21点为例, 这个状态就是从 16点的再来一张牌小于21点概率, 推算出15点再来一张牌小于21点概率. 这一步就能得到comment 里面out time的题.
然后提取公式, 找出简化公式

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:

        #n = 21  # prob point
        #k = 17  # draw less than
        #maxPts = 10  # card

        '''
        dp = [0 for i in range(k)] 
        dp += [1 for i in range(k, n+1,1)] 
        dp += [0 for i in range(n+1, n*2,1)] 

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

        return dp[0]
        '''

        dp = [0.0] * (2*n + maxPts )

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

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

        return dp[0]

biancaone commented 3 years ago

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

wangyifan2018 commented 3 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
        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]

JK1452470209 commented 3 years ago

思路

dp+滑动窗口

代码

    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)

Leonalhq commented 3 years ago

思路

没什么思路

居然是转移方程式：分数大于等于 K 的这些情况中不大于 N 的概率

dp[i] = sum(dp[i+j] for j in range(1,W+1)/W

算法

def nuw21Game(self, N:int, K:int, W:int):

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]

Dp 就是linear time和sapce 啦！

weichuliao commented 3 years ago

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]

joeytor commented 3 years ago

思路

dp[i] 代表有 i 分时赢得概率

base case

当 $i \in [k, min(n, k+maxPts-1]$ 时, dp[i] = 1 (题目定义)

当 $i \in [min(n, k+maxPts-1, )$ 时, dp[i] = 0 (题目定义)

动态转移

因为每次可能得到的数是 [1, maxPts] 而且每个数是相同 probability 的, 所以 dp[i] 的概率就是后面 maxPts 个数的赢得概率除以 maxPts

dp[i] = sum(dp[i+1:i+maxPts]) / maxPts

可以用滑动窗口优化上面的 sum 的求解, 每次加入一个新的数组并移除末端的数字

return

dp[0] 代表有 0 分时赢得概率

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:

        # dp[i] is the probability of winning when Alice have i points
        dp = [0] * (k+maxPts)
        w = 0
        for i in range(k+maxPts-1, -1, -1):
            if i >= k:
                # if i >= k, then the probability depends on if i <= n based on question
                dp[i] = 1 if i <= n else 0
                w += dp[i]
            else:
                # if i < k, then the number outcome [1, maxPts] have equal probability
                # so p[i] = sum(p[i+1:i+maxPts]) / (maxPts)
                # use sliding window approach to calculate
                dp[i] = w / maxPts
                w = w + dp[i] - dp[i+maxPts]

        return dp[0]

复杂度

时间复杂度: O(k+maxPts) dp 数组的遍历复杂度, 每次复杂度是 O(1)

空间复杂度: O(k+maxPts) dp 数组的空间复杂度

muimi commented 3 years ago

思路

从后往前动态规划，以及滑块

代码

class Solution {
  public double new21Game(int n, int k, int maxPts) {
    double[] dp = new double[k + maxPts];
    double sum = 0;
    for (int i = k; i < dp.length; i++) {
      dp[i] = i > n ? 0 : 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];
  }
}

复杂度

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

Richard-LYF commented 3 years ago

class Solution: def new21Game(self, n: int, k: int, maxPts: int) -> float: W= maxPts K=k N=n 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]

ai2095 commented 3 years ago

LC837. New 21 Game

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

Topics

slide window
dp

思路

dp + slide window

代码 Python

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

复杂度分析

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

zhiyuanpeng commented 3 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]

LareinaWei commented 3 years ago

Thinking

DP + sliding window

Code

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

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

Complexity

Time complexity: O(n). Space complexity: O(n)

james20141606 commented 3 years ago

Day 44: 837. New 21 Game (dynamic programming, probability, sliding window)

Problem Link
- 837. New 21 Game
Ideas
- It's a very interesting probability question, which could be solved by dynamic programming. The essence of this problem is to abstract the question into a probability formula. Using the law of total probability, we now that if we have i points now, the probability of wining the game is: $P(x)=\frac{\sum{i=1}^{\operatorname{maxPts}} P(x+i)}{\operatorname{maxPts}}$. This step is easy to understand. Then we need to implement it using dynamic programing. We should notice that if $k \leq x \leq \min (n, k+\operatorname{maxPts}-1)$ then $d p[x]=1$, if $x>\min (n, k+\operatorname{maxPts}-1)$ then $d p[x]=0$. $\operatorname{maxPts}-1)$ is the largest points we could reach. So we only need to care about points less than k, and use the total probability to compute the probability, in reversed order. This will cause TLE, because we repeatedly calculate some probability while we could only care about the edge. So we use difference to have $d p[x]=d p[x+1]-\frac{d p[x+\operatorname{maxPts}+1]-d p[x+1]}{\operatorname{maxPts}}$ for $0 \leq x<k-1$. for $k-1$ we have $d p[k-1]=\frac{\sum{i=0}^{\operatorname{maxPts}-1} d p[k+i]}{\operatorname{maxPts}}$. From above we could easily have: $d p[k-1]=\frac{\min (n, k+\operatorname{maxPts}-1)-k+1}{\operatorname{maxPts}}=\frac{\min (n-k+1, \operatorname{maxPts})}{\operatorname{maxPts}}$. The rest part could be calculated through state transition.
Complexity: hash table and bucket
- Time: O(min(n,k+maxPts)) (before optimization it is O(n+k×maxPts))
- Space: O(k+ maxPts)
Code

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]

other resources:
- https://leetcode-cn.com/problems/new-21-game/solution/xin-21dian-by-leetcode-solution/
- https://leetcode-cn.com/problems/new-21-game/solution/zen-yang-de-dao-guan-fang-ti-jie-zhong-de-zhuang-t/

florenzliu commented 3 years ago

Explanation

dp + sliding window
dp[i]: the probability that Alice's score (i.e., i) is not greater than N
dp[i] = (dp[i+1] + dp[i+2] + ... + dp[i+W]) / W
The objective is to get the score x where K <= x <= N

Python

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

        curr_sum = 0
        for i in range(K, K+W):
            if i <= N:
                dp[i] = 1
            curr_sum += dp[i]

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

        return dp[0]

Complexity:

Time Complexity: O(K+W)
Space Complexity: O(K+W)

carsonlin9996 commented 3 years ago

不太会dp，看了解答才大概会。。继续研究


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 3 years ago

思路

主要需要搞清楚概率计算。如果【1-10】范围可选卡片，抽到1-10的概率为1/10。当我们要计算最后得到5的概率，可以是[1 +4 ] + [2 +3 ] + [3 +2] + [4 +1] + [0 5] 因此递推关系为dp[i] = sum(j from 1 maxPts) [i-j] * 1/maxPts. 采用dp方法计算所有点的概率。最后需要求解的概率为 sum(i from k to n) dp[i]，方法1，采用暴力解，时间的复杂度为O( N* maxPoint) N 为能抽到的最大点。空间复杂度为 O(N)。该方法不能pass，有 RTE。方法2，进一步优化，采用滑动窗口，固定滑动窗口大小为maxPts。每次移动窗口，减去dp[i - maxPts-1]，当计算dp[i] 加入sum。时间复杂度为O(N) N为能抽到的最大点，空间复杂度为O(N)。

关键点

代码

语言支持：C++

C++ Code:


        int maxPoint = max(k -1 + maxPts, n) ; 
        vector<double> dp(maxPoint+1); 
        dp[0] =1.0;  // base case.       
        for(int i=1; i<=maxPoint; i++)
        {
            for(int j = i - maxPts; j<i; j++)
            {
               if(j>=0 && j < k) 
                 dp[i] += (dp[j] * 1.0/maxPts); 
            }
        }
        double ret =0; 
        for(int i = k; i<=n; i++)
        {
            ret +=dp[i];
        }

        return ret;

        if( k == 0 || n >= k + maxPts)
            return 1;        
        int maxPoint = max(k -1 + maxPts, n) ; 
        vector<double> dp(maxPoint+1); 
        dp[0] =1.0;  // base case.  
        double sum =1;

        for(int i =1; i<=min(maxPts, maxPoint ); i++)
        {
            dp[i] = sum/maxPts;
            if(i<k)
               sum +=dp[i]; 
        }
        for(int i = maxPts+1; i<=maxPoint; i++)
        {
            sum -=dp[i - maxPts-1];
            dp[i] = sum/maxPts; 
            if(i<k)
                sum +=dp[i]; 
        }
//        for(int i=1; i<=maxPoint; i++)
//        {
 //           for(int j = i - maxPts; j<i; j++)
//            {
//               if(j>=0 && j < k) 
//                 dp[i] += (dp[j] * 1.0/maxPts); 
//            }
//        }
        double ret =0; 
        for(int i = k; i<=n; i++)
        {
            ret +=dp[i];
        }

        return ret;

Menglin-l commented 3 years ago

学习了题解的做法。。。

代码部分：

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

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

        dp[k - 1] = 1.0 * Math.min(maxPts, n - k + 1) / 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];
    }

}

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

【Day 44 】2021-10-23 - 837. 新 21 点 #61

837. 新 21 点

入选理由

题目地址

前置知识

题目描述

思路:

如何使用动态规划来考虑本题?

方法: 动态规划 + 滑动窗口优化

代码:

复杂度分析

思路

代码(C++)

复杂度分析

DP+ sliding window (I checked the solution)

思路

代码

思路

代码

复杂度分析

题目

思路

代码

复杂度分析

时间复杂度

空间复杂度

思路

代码

复杂度

思路

Python3

思路1 - DFS TLE

Java Code

时间&空间

思路2 - DP TLE

Java Code

时间&空间

思路3 - DP + 滑动窗口

Java Code

时间&空间

Idea:

Code:

Complexity:

思路

代码

link:

代码 Javascript

思路

代码

题目

思路

代码

复杂度

代码

复杂度

代码

复杂度

思路

代码

复杂度

思路

代码

复杂度分析

837. 新 21 点

入选理由

题目地址

前置知识

题目描述

动态规划略显还是不够，保留滑动窗口结果不重复计算才是王道

Solution1

Solution2

thoughts

code

complexity

思路

代码

dp[i] = (dp[i+1] + dp[i+2] + ... + dp[i+W]) / W

最后没有过, 不过大概思路是对的.

思路