# -*- coding: utf-8 -*-
"""
 @Time    : 2020/6/3 10:51
 @Author  : QDY
 @FileName: 837. 新21点_动态规划.py

    爱丽丝参与一个大致基于纸牌游戏 “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

"""


class Solution:
    def new21Game(self, N, K, W):
        if K == 0: return 1.0
        # dp[i] = 得分为i时，再抽，最后不少于K时停止，分数不超过K的概率
        dp = [0.0] * (K + W + 1)
        for i in range(K, min(N + 1, K + W + 1)):
            dp[i] = 1.0
        # K~N之间的(N-K+1个)数都满足，但不能超过W个
        dp[K - 1] = float(min(N - K + 1, W)) / W
        # dp[i] = (dp[i+1]+...+dp[i+W])/W
        # dp[i+1] = (dp[i+2]+...+dp[i+W+1])/W
        # dp[i] - dp[i+1] = (dp[i+1]-dp[i+W+1])/W
        # dp[i] = dp[i+1] + (dp[i+1]-dp[i+W+1])/W
        for i in range(K - 2, -1, -1):
            dp[i] = dp[i + 1] - (dp[i + W + 1] - dp[i + 1]) / W
        return dp[0]
