Re: [閒聊] 每日LeetCode

[pandix (麵包屌)]

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
推 Rushia: 看不懂題目 我流淚了
推 ekids1234: e04 這題我來回寫來回想花了幾個小時 = = 我菜
→ ekids1234: 直接看 top down 的 code 看不懂  看了 bottom up 說明
→ ekids1234: 也看不懂    後來看到有講解的 top down 才能接受
※ 編輯: pandix (123.252.3.181 臺灣), 05/26/2023 07:08:13