Re: [閒聊] 每日LeetCode已回收
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~n] 都是 100% = 1.0 因為已經贏了
dp[n+1~] 就爆掉了 0% = 0
要算的就是 i < k 的那些 i 的勝率
最後題目要的就是 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]
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.252.3.181 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1685025499.A.214.html
推
05/25 22:42,
2年前
, 1F
05/25 22:42, 1F
推
05/25 22:48,
2年前
, 2F
05/25 22:48, 2F
→
05/25 22:49,
2年前
, 3F
05/25 22:49, 3F
→
05/25 22:49,
2年前
, 4F
05/25 22:49, 4F
※ 編輯: pandix (123.252.3.181 臺灣), 05/26/2023 07:08:13
討論串 (同標題文章)
完整討論串 (本文為第 330 之 719 篇)：