新21点
问题描述：
爱丽丝参与一个大致基于纸牌游戏 “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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/new-21-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。大体思路
当爱丽丝手里的牌大于等于k时就停止抽牌，求解其最终手牌点数小于等于N的概率。由于该问题带有条件概率，因此不能简单地使用dfs列举出所有可能取值，用小于N结果数目除以总数目。
如下以W = 3， N = 3， K = 2为例说明
可以抽出如下几种情况
情况（第一次 第二次） 概率
1 1 1/3*1/3
1 2 1/3*1/3
1 3 1/3*1/3
2 1/3
3 1/3dfs思路
我们定义函数dfs(sum)为当前值为sum，在题目抽牌条件下，最终结果小于等于N的概率。我们可以得到递推式为：
递归出口：
sum>=k时即不能抽的时候，此时sum大于N返回0，sum小于等于N返回1。
实现代码如下：
public double dfs(int sum, int N, int K, int W){
if(sum >= K){
return sum <= N ? 1.0 : 0.0;
}
double ans = 0.0;
for(int i = 1; i <= W; i++){
ans += dfs(sum + i, N, K, W) / W;
}
return ans;
}动态规划
与dfs大体思路相同，定义一大小为K + M长的double型数组dp, dp[i]为当前值为i，最终分数不超过N的概率。由于我们可以进行抽牌的最大手牌数为K - 1，则其最终最大手牌数为K + M - 1，因此定义K + M长的数组。
转移方程：
baseline:
class Solution {
public double new21Game(int N, int K, int W) {
double[] dp = new double[K + W];
for(int i = K; i < dp.length; i++){
if(i > N){
break;
}
dp[i] = 1;
}
for(int i = K - 1; i >= 0; i--){
for(int j = 1; j <= W; j++){
if(i + j > N){
break;
}
dp[i] += dp[i + j] / W;
}
}
return dp[0];
}
}时间复杂度为0（K * W）
优化后的dp
从上一节可知：
因此可以由该式推出如下式子：
由于i的最大取值为K - 1，其转移方程中最大要用到dp[K + W]的值，而我们的dp下标最大取值为K + W - 1，因此baseline中应该先利用上一节的递推公式计算出dp[K - 1]的值，然后从K-2往前递推。
实现代码如下：
class Solution {
public double new21Game(int N, int K, int W) {
if(K == 0){
return 1.0;
}
double[] dp = new double[K + W + 1];
for(int i = K; i < dp.length; i++){
if(i > N){
break;
}
dp[i] = 1;
}
for(int j = 1; j <= W; j++){
dp[K - 1] += dp[K - 1 + j] / W;
}
for(int i = K - 2; i >= 0; i--){
dp[i] = (dp[i + 1] + W * dp[i + 1] - dp[i + 1 + W]) / W;
}
return dp[0];
}
}时间复杂度为O（W + K）
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-07-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
