0837. New 21 Game

题目信息

题号:

0837

难度:

Medium

主题:

概率、随机得分、停止条件

原题:

LeetCode 0837

重点:

总分小于 k 时继续等概率抽取 1 至 maxPts,达到或超过 k 后立即停止;求最终总分不超过 n 的概率

题目重述

Alice 初始得分为 0。当当前总分严格小于 k 时,她会独立且等概率地从 1 到 maxPts 中抽取一个整数,并把它加入总分;一旦总分达到或超过 k,游戏立即停止,不再抽取。

请返回游戏结束时 Alice 总分不超过 n 的概率。若 k == 0,游戏从一开始就停止。答案与真实值的误差在 10^-5 以内即可接受。

0 <= k <= n <= 10^4,1 <= maxPts <= 10^4。

自建示例

部分终局超过上界:

输入:n = 2, k = 2, maxPts = 2
输出:0.75
解释:第一次抽到 2 的概率为 1/2,直接以总分 2 成功;第一次抽到 1 后,再抽到 1 的概率为 1/4,以总分 2 成功,抽到 2 则以总分 3 失败,因此成功概率为 1/2 + 1/4 = 0.75。

阈值为零时立即停止:

输入:n = 0, k = 0, maxPts = 7
输出:1.0
解释:k 达到允许的最小值 0,Alice 初始得分 0 已经不小于 k,因此不会抽取任何数字。最终得分 0 不超过 n = 0,成功概率为 1。