新21点

837. 新 21 点 - 力扣

---

题型描述

一维概率DP

题目描述&数据范围

$1\leq k\leq n\leq10^4$

$1\leq maxPts\leq10^4$

题解

由于 $maxPts$ 不好书写，下文记录为 $W$

记录$dp[i]$ 表示得分为 $i$ 时，抽取到结束后得分不超过 $n$ 的概率

显然边界条件为：在 $[k,k+w-1]$ 的范围内，$dp[i]$ 的值要么是 $1$ 要么是 $0$

转移为:
$$
dp[i]=\sum_{k=1}^{w}dp[i+k]
$$
而这样转移会达到 $O(n*w)$ 的复杂度

注意到求和的区间为 $[i+1,i+w]$ 所以可以记录一个区间和 $sum$

每次更新 $sum$ 即可：
$$
sum=sum+dp[i]-dp[i+w]
$$

代码

class Solution {
public:
    double dp[20007];//dp[i]表示得分为i时，进行到结束的概率
    double new21Game(int n, int k, int w) {
        double sum=0;
        for(int i=k;i<=k+w-1;++i){
            if(i<=n)dp[i]=1;
            sum+=dp[i];
        }
        int r=k+w-1,l=k;
        for(int i=k-1;i>=0;--i){
            dp[i]=sum/w;
            l--;
            sum=sum-dp[r]+dp[l];
            r--;
        }
        return dp[0];
    }
};