跳到主要内容

837.新21点

链接：837.新21点
难度：Medium
标签：数学、动态规划、滑动窗口、概率与统计
简介：爱丽丝参与一个大致基于纸牌游戏 “21 点” 规则的游戏，描述如下：爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。每次抽取都是独立的，其结果具有相同的概率。当爱丽丝获得不少于 K 分时，她就停止抽取数字。爱丽丝的分数不超过 N 的概率是多少？

题解 1 - typescript

编辑时间：2020-06-03
执行用时：220ms
内存消耗：41.6MB
编程语言：typescript
解法介绍：优化题解 1。

function new21Game(N: number, K: number, W: number): number {
  const dp = new Array(W).fill(0);
  let sum = 0;
  for (let i = K; i <= N && i <= K + W - 1; i++) {
    dp[i - K] = 1;
    sum++;
  }
  for (let i = K - 1; i >= 0; i--) {
    dp.unshift(sum / W);
    sum += dp[0] - dp.pop();
  }
  return dp[0];
}

题解 2 - typescript

编辑时间：2020-06-03
执行用时：1396ms
内存消耗：38.1MB
编程语言：typescript
解法介绍：dp[x]=积分为 x 时的概率，dp[x]=sum(dp[x+1]+dp[x+2]...+dp[x+W])/W。

function new21Game(N: number, K: number, W: number): number {
  const arr = new Array(K + W).fill(0);
  const min = Math.min(N, K + W - 1);
  for (let i = K; i <= min; i++) arr[i] = 1;
  for (let i = K - 1; i >= 0; i--) {
    let s = 0;
    for (let j = i, sum = i + W; j <= sum; j++) s += arr[j];
    arr[i] = s / W;
  }
  return arr[0];
}

题解 3 - typescript

编辑时间：2020-06-03
执行用时：264ms
内存消耗：41.8MB
编程语言：typescript
解法介绍：优化题解 2。

function new21Game(N: number, K: number, W: number): number {
  const dp = new Array(W).fill(0);
  const min = Math.min(N, K + W - 1);
  let sum = -1;
  while (sum + K <= min) dp[sum++] = 1;
  for (let i = K - 1; i >= 0; i--) {
    dp.unshift(sum / W);
    sum += dp[0] - dp.pop();
  }
  return dp[0];
}

题解 1 - typescript
题解 2 - typescript
题解 3 - typescript