## [837\. 新21點](https://leetcode-cn.com/problems/new-21-game/) > Medium #### 思路 首先進行**閱讀理解**： * 從0開始抽卡，然后累加抽到卡的積分 * 卡片的數字是 `$ [1, W] $` * 積分`$ <K $`， 不繼續抽牌，積分`$ >=K $`時停止抽牌 * 停止抽牌后，積分`$ <=N $` 獲勝， 積分`$ >N $` 失敗 閱讀理解結束，開始**思考過程**： * 對于 `$ [1, W] $` 的卡片，抽取每張卡片的概率都是 `$ 1/W $` * 想要和在范圍中，那就是抽取這些組合的概率和。舉個栗子，就清楚了： ``` 擲兩次骰子，求兩次骰子和在4-6之間的概率 4的可能的組合為: (1,3)、(2,2)、(3,1) 5的可能的組合為: (2,3)、(3,2) 6的可能的組合為: (1,5)、(2,4)、(3,3)、(4,2)、(5,1) P(sum) = P(4) + P(5) + P(6) = 3/36 + 2/36 + 5/36 = 5/18 ``` * 對于我們這道題，如果和`$ <K $` ，我們還要繼續抽卡，這樣就是 `$ 1/W $` 還要在乘上后面的概率。就類似我們上面擲骰子例子中擲骰子的次數。 * 所以遞歸終止條件為`當前和 >= K ` * 遞歸結束后，假如在N的范圍里和最后一次的概率為1，代表結束抽卡之后結果必定成功概率為100%，反之為0 使用記憶化遞歸，TLE python3 ``` class Solution: @lru_cache(None) def dfs(self, cur, N, K, W): if cur >= K: if cur <= N: return 1 else: return 0 sum = 0 for i in range(1, W+1): sum += 1.0 / W * self.dfs(cur + i, N, K, W) return sum def new21Game(self, N: int, K: int, W: int) -> float: return self.dfs(0,N,K,W) ``` **TLE，需要更新思路** 記憶化遞歸通常我們可以轉成dp，bottom-up方式來優化。 **拜讀大佬解法，獲得新思路** * 類似于動態規劃爬樓梯解題的思路，想要爬到第i階，要么是從i-1過來，要么是從i-2過來 * 對于我們這道題最終要使和為i，那必然是從`$ [i-1,i-W] $`這個區間跳過來的 ##### 概率分析 * 已有i-1，再抽1，最終為i * 已有i-2，再抽2，最終為i * ... * 以后i-W，再抽W，最終為i * i的概率，`$ P(i) = P(i-1) * 1/W + P(i-2) * 1/W...P(i-W) * 1/W = (P(i-1)+... + P(i-W)) * 1/W $` ##### 動態規劃 * 前面的概率決定了當前狀態，后面的狀態不會影響當前狀態，具有后無效性，可以進行狀態轉移，使用動態規劃。 * 定義dp數組，`dp[i]`表示和為i的概率。 * dp數組的長度為`N+1`，代表和為`0~N`的概率。題目是求解 `N` 范圍內的概率，所以后面的不用考慮 * **狀態轉移**：`$ \displaystyle{dp[i] = (\sum_{k=i-W}^{i-1} dp_{k}},i\le K) * 1/W $` * 求和過程中需要保證i <= K也就是，應為>K 的已經結束了，概率已經確定，不需要計算在后面的概率中 * 最終結果為 `$ result = \displaystyle{\sum_{k=K} ^ N}dp_{k} $` 綜上，進行嘗試，TLE。我真的是太難了。。 python3 ``` class Solution: def new21Game(self, N: int, K: int, W: int) -> float: dp = [None] * (N + 1) dp[0] = 1 for i in range(1, N + 1): left = 0 if (i-W) < 0 else (i-W) right = i if i <= K else K dp[i] = sum(dp[left:right]) * (1/W) return sum(dp[K:]) ``` **還需進行優化** * `dp[i]` 求`$ [i-W,i-1] $`范圍的值，雖然每次都向右移動了一個，但是還是整個遍歷求和了。 * 使用滑動窗口，中間部分不重復計算，只判斷頭尾元素。 綜上，進行嘗試，AC！ #### 代碼 python3 ``` class Solution: def new21Game(self, N: int, K: int, W: int) -> float: dp = [None] * (N + 1) dp[0] = 1 presum = 0 for i in range(1, N + 1): if i-W > 0: presum -= dp[i-W-1] if i <= K: presum += dp[i-1] dp[i] = presum * (1/W) return sum(dp[K:]) ```