题目要求
算法分析
题意: 从0点数开始,等可能加上1到W之间的某一数值,如果点数小于等于K,继续抽牌,一旦点数大于K则停止抽牌,并判断点数是否超过N，没超过N就获胜。本题求获胜的概率
整局游戏所有可能出现的点数范围是 0 到 W+K-1,可以用长度为W+K的数组res存储处于各点数时游戏获胜的概率
其中,点数从K到W+K-1之间时,获胜的概率是100%,
点数处于从W+K-1到N是,获胜的概率是0,
点数为n时获胜的概率是: res[n] = res[n+1]/w + res[n+2]/w + ....... res[n+w]/w
求res[n-1]时,不必计算每一个后续值,可以用res[n-1] = res[n] + res[n]/w - res[n+w]/w求
代码展示(C#)
public class Solution {
public double New21Game(int N, int K, int W) {
double[] res = new double[W + K];
double window = 0;
for (int i = K + W - 1; i >= K; i--)
{
if (i > N)
{
res[i] = 0;
}
else
{
res[i] = 1;
}
window += res[i];
}
for(int i = K - 1; i >= 0; i--)
{
res[i] = window / W;
window = window + res[i] - res[i + W];
}
return res[0];
}
}
提交结果
LeetCode0837.新21点
原文：https://www.cnblogs.com/KingR/p/13037376.html
