題目:
Alice plays the following game, loosely based on the card game "21".
Alice starts with 0 points and draws numbers while she has less than k points. During each draw, she gains an integer number of points randomly from the range [1, maxPts], where maxPts is an integer. Each draw is independent and the outcomes have equal probabilities.
Alice stops drawing numbers when she gets k or more points.
Return the probability that Alice has n or fewer points.
| class Solution(object): def new21Game(self, n, k, maxPts): # Corner cases if k == 0: return 1.0 if n >= k - 1 + maxPts: return 1.0 # dp[i] is the probability of getting point i. dp = [0.0] * (n + 1) # [0.0, 0.0, ..., 0.0] = (n + 1) * [0.0] probablity = 0.0 # dp of n or less point totalSum = 1.0 # sum of curr dp[0] = 1.0 for i in range(1, n + 1): dp[i] = totalSum / maxPts if i < k: totalSum += dp[i] else: probablity += dp[i] if i >= maxPts: totalSum -= dp[i - maxPts] return probablity sol = Solution() print(sol.new21Game(21, 17, 10)) # time complexity = O(n) # n is the range of the number, it's linear. |
先初始化每個可能性的機(jī)率和總和dp，之後對每個dp做抽牌總和不大於n的機(jī)率，之後再把所有機(jī)率總合起來，就完事了。
不過腦袋要燒壞了，我覺得我需要找一件事情就認(rèn)真做到底，不然要沒生產(chǎn)力了。
時間複雜度為 O(n)，其中 n 是遊戲中的數(shù)字範(fàn)圍。因?yàn)樵谵捜χ?，我們迭代了?1 到 n 的所有數(shù)字，並對每個數(shù)字執(zhí)行一些固定的操作。因此，整個程式的時間複雜度是線性的。
