leetcode之每日一题

leetcode 837

新21点

Posted by Static on June 3, 2020

题目链接:https://leetcode-cn.com/problems/new-21-game/

题目描述

分析

参考官网:分析

代码实现

public enum Q837 {
    instance;

    // 少于 k,从[1,W]抽取,累计之和不超过N，可再次抽取
    public double new21Game(int N, int K, int W) {
        double[]dp=new double[N+1];
        double sum=0;
        dp[0]=1;
        if(K>0) sum+=1;
        for(int i=1;i<=N;i++){
            dp[i]=sum/  W;
            if(i<K) sum+=dp[i];
            if(i>=W) sum-=dp[i-W];
        }
        double ans=0;
        for(int i=K;i<=N;i++) ans+=dp[i];
        return ans;
    }

    public static void main(String[] args) {
        // assert 0.73278
        System.out.println(Q837.instance.new21Game(21,17,10));
    }
}