837. New 21 Game
题目好复杂 总之就是玩21点 庄家点数 k 点数上限不是 21 是 n
一张牌最大有可能是 maxPts
问你这种状况下的胜率 也就是点数大于 k 小于等于 n 的机率是多少
Example 1:
Input: n = 10, k = 1, maxPts = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.
Example 2:
Input: n = 6, k = 1, maxPts = 10
Output: 0.60000
Explanation: Alice gets a single card, then stops.
In 6 out of 10 possibilities, she is at or below 6 points.
Example 3:
Input: n = 21, k = 17, maxPts = 10
Output: 0.73278
思路:
1.DP状态转移 假设 dp[i] 代表点数是 i 的时候的胜率
dp[k+1~n] 都是 100% = 1.0 因为已经赢了
dp[n+1~] 就爆掉了 0% = 0
要算的就是 i 小于等于 k 的那些胜率
最后题目要的就是 dp[0] 也就是从 0 开始抽牌的胜率
2.dp[i] 要怎么算? 用题目的 maxPts = 10 当例子
抽到 +1 ~ +10 的机率都一样是 1/maxPts
所以 dp[i] 到 dp[i+1] ~ dp[i+10] 的机率都一样
胜率就是骰到他们的机率乘上他们各自的胜率
也就是 dp[i] = dp[i+1]*1/maxPts + dp[i+2]*1/maxPts + ...
所以就从 i=k~0 traverse 一次就好
dp[i] 可以化简成 sum(dp[i+1~i+maxPts]) / maxPts
维护一段区间的 sum 就可以 O(n) 算到 dp[0]
Python code:
class Solution:
def new21Game(self, n: int, k: int, maxPts: int) -> float:
dp = [0]*(max(n,k)+maxPts+1)
for i in range(k, n+1):
dp[i] = 1
prob = sum(dp[k:k+maxPts])
for i in range(k-1, -1, -1):
dp[i] = prob / maxPts
prob += dp[i] - dp[i+maxPts]
return dp[0]