837. New 21 Game
你版人都去C106, 剩我在寫這該死的東西
思路:
k = 0 或是 k - 1 + maxPts < n 直接回傳1
再來就是dp + sliding window
dp[i] 表示目前分數是i的機率
dp[i] = (dp[i-maxPts] + dp[i-maxPts+1] + ... + dp[i-1]) / maxPts
等式右邊那坨可以用sliding window, 不用每次都重加
然後注意 i > k後就別算了
接著dp[k] ~ dp[n]的總和就是答案
golang code
func new21Game(n int, k int, maxPts int) float64 {
if k == 0 || k-1+maxPts < n {
return 1.0
}
dp, l := make([]float64, n+1), 0
dp[0] = 1.0
prevSum, ans := 1.0, 0.0
for i := 1; i <= n; i++ {
if i > l+maxPts && l < k { //注意 l>=k就不要扣了, 會多扣
prevSum -= dp[l]
l++
}
dp[i] = prevSum / float64(maxPts)
if i < k {
prevSum += dp[i]
} else {
ans += dp[i]
}
}
return ans
}