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]