新 21 点
难度:
标签:
题目描述
Alice plays the following game, loosely based on the card game "21".
Alice starts with 0 points and draws numbers while she has less than k points. During each draw, she gains an integer number of points randomly from the range [1, maxPts], where maxPts is an integer. Each draw is independent and the outcomes have equal probabilities.
Alice stops drawing numbers when she gets k or more points.
Return the probability that Alice has n or fewer points.
Answers within 10-5 of the actual answer are considered accepted.
Example 1:
Input: n = 10, k = 1, maxPts = 10 Output: 1.00000 Explanation: Alice gets a single card, then stops.
Example 2:
Input: n = 6, k = 1, maxPts = 10 Output: 0.60000 Explanation: Alice gets a single card, then stops. In 6 out of 10 possibilities, she is at or below 6 points.
Example 3:
Input: n = 21, k = 17, maxPts = 10 Output: 0.73278
Constraints:
0 <= k <= n <= 1041 <= maxPts <= 104
代码结果
运行时间: 49 ms, 内存: 16.4 MB
/*
* 思路：
* 1. 使用动态规划来计算每个分数出现的概率。
* 2. 定义dp[i]为分数为i的概率。
* 3. 初始时，dp[0] = 1。爱丽丝开始时得分为0。
* 4. 当i < k时，dp[i] = (dp[i-1] + dp[i-2] + ... + dp[i-maxPts]) / maxPts。
* 5. 当i >= k时，停止抽牌，dp[i] = dp[i-1]。
* 6. 我们需要计算所有dp[i] (k <= i <= n)的和，这就是答案。
*/
import java.util.stream.IntStream;
public class Solution {
public double new21Game(int n, int k, int maxPts) {
if (k == 0 || n >= k + maxPts) return 1.0;
double[] dp = new double[n + 1];
dp[0] = 1.0;
double sum = 1.0;
for (int i = 1; i <= n; i++) {
dp[i] = sum / maxPts;
if (i < k) sum += dp[i];
if (i >= k) sum -= dp[i - maxPts];
}
return IntStream.range(k, n + 1).mapToDouble(i -> dp[i]).sum();
}
}解释
方法:
这个题解使用动态规划来解决问题。首先，如果n大于等于k+p-1，意味着爱丽丝可以在不超过n的情况下达到或超过k分，因此返回1.0。对于其他情况，使用一个大小为k+p的数组dp来存储在每个得分i处获得得分不超过n的概率。初始化dp数组中k到n的索引值为1.0，因为这些得分直接导致游戏停止且不会超过n。然后，从k-1倒推到0计算每个得分的概率，使用滑动窗口和cur来跟踪累计概率，以减少重复计算，提高效率。
时间复杂度:
O(k+p)
空间复杂度:
O(k+p)
代码细节讲解
🦆
为什么在解释题解时提到，如果n大于等于k+p-1就可以直接返回1.0？这个条件是怎样推导出来的？
▷🦆
在动态规划数组dp中，为何初始化索引k到n的值为1.0？这样初始化有何依据？
▷🦆
请问如何理解题解中提到的`滑动窗口和cur来跟踪累计概率`的操作？它具体是如何实现的？
▷