LeetCode-837 新 21 点

Table of Contents

LeetCode-837 新 21 点 #

Solution 1 #

记 $dp[i]$ 为初始分数为 $i$, 最终得分在 $[k, n]$ 的概率. 状态转移方程为: $$ dp[i] = \frac{1}{\text{maxPts}}\sum_{j=i + 1}^{i + \text{maxPts}}dp[j] $$

代码如下:

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp = [0 for _ in range(k + maxPts)]
        for i in range(k, k + maxPts):
            dp[i] = 1 if i <= n else 0
        s = sum(dp[k:])
        for i in range(k - 1, -1, -1):
            dp[i] = s / maxPts
            s = s - dp[i + maxPts] + dp[i]
        return dp[0]