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
}