Re: [閒聊] 每日leetcode
甚麼郩啦
幹
我真的很挫折
一二三四五
; ;
def new21Game(self, n: int, k: int, maxPts: int) -> float:
dp = [0.0 for _ in range(n+1)]
# O(N^2)
# dp[0] = 1.0
# p = 1/maxPts
# for i in range(0, k):
# for pts in range(1, maxPts+1):
# dp[i+pts] += (dp[i]*p)
# return sum(dp[k:n+1])
# O(N)
dp[0] = 1.0 #init
window_sum = 1.0 if k>0 else 0.0 # = dp[i-1]+...+dp[i-maxPts] when
[i-maxPts,i-1] in [0,k], which is valid probability
for i in range(1,n+1):
dp[i] = window_sum/maxPts
if i<k:
window_sum += dp[i]
if 0<=(i-maxPts)<k:
window_sum -= dp[i-maxPts]
return sum(dp[k:])
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.58.28 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1755439512.A.A22.html
推
08/17 22:05,
3月前
, 1F
08/17 22:05, 1F
→
08/17 22:06,
3月前
, 2F
08/17 22:06, 2F
推
08/17 22:09,
3月前
, 3F
08/17 22:09, 3F
※ 編輯: DJYOMIYAHINA (220.132.58.28 臺灣), 08/17/2025 22:13:48
推
08/17 22:13,
3月前
, 4F
08/17 22:13, 4F
→
08/17 22:13,
3月前
, 5F
08/17 22:13, 5F
→
08/17 22:13,
3月前
, 6F
08/17 22:13, 6F
推
08/17 22:16,
3月前
, 7F
08/17 22:16, 7F
→
08/17 22:17,
3月前
, 8F
08/17 22:17, 8F
討論串 (同標題文章)
完整討論串 (本文為第 1502 之 1548 篇)：