[leetcode 837][概率][滑动窗口][DP]新21点

题目链接

leetcode 837 新21点

解题思路

该题目的就是求当爱丽丝到达k点后的所有可能中点数在[k,n]的概率

DP(超时)

设dp[i]表示从开始到点数i的概率，初始值dp[0] = 1，例如maxPts = 10, k = 5，那么dp[1] = 0.1, dp[2] = 0.11, dp[3] = 0.121

算出dp[1]到dp[k+maxPts-1](最高只能到达k+maxPts-1)后，结果就等于

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func new21Game(n int, k int, maxPts int) float64 {
	var dp = make([]float64, k+maxPts)
	dp[0] = 1
	for i := range k {
		for j := 1; j <= maxPts; j++ {
			dp[i+j] += dp[i] / float64(maxPts)
		}
	}
	sum1 := float64(0)
	sum2 := float64(0)
	for i := k; i < k+maxPts; i++ {
		if i <= n {
			sum1 += dp[i]
		}
		sum2 += dp[i]
	}
	return sum1 / sum2
}

上述代码时间复杂度为,当k和maxPts都很大时会超时

滑动窗口+DP

设dp[i]表示从i开始到达[k, n]的概率，例如k = 5, n = 7, dp[3]就表示从点数3开始到[k,n]的概率，从dp[k]开始反推（dp[n]到dp[k]概率都为1），dp[0]就是结果，dp[i]转移方程为

设滑动窗口长度固定左边界为i+1右边界为i+maxPts，那么滑动窗口内的值和就为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func new21Game(n int, k int, maxPts int) float64 {
	var dp = make([]float64, n+1)
	var s float64 = 0
	for i := n; i >= 0; i-- {
		if i >= k {
			dp[i] = 1
		} else {
			dp[i] = s / float64(maxPts)
		}
		s += dp[i]
		if n-i+1 > maxPts {
			s -= dp[i+maxPts]
		}
	}
	return dp[0]
}

上述代码时间复杂度为