837. New 21 Game [经典DP, 依赖前N项]

https://leetcode.com/problems/new-21-game/
很典型的DP题目，有必要掌握。

个人解答

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        # edge case
        if K == 0 or N >= K + W:
            return 1
        pWSum = 1. # prev W probablilities sum 
        ps = [1.] # ps[i]: probabilities to reach i
        for i in range(1, N + 1):
            p = pWSum / W
            ps.append(p)
            if i < K:
                pWSum += p
            if i - W >= 0:
                pWSum -= ps[i - W]
        return sum(ps[K:])

题目分析

参考：https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP-O(N))
这是一类很典型的DP题目，代表：爬楼梯。
当前状态依赖前N项的状态，N表示最长的步长（比如最多爬几阶楼梯）。

比如这道题中，DP关系就是：
到达当前位置的概率，是前W个位置概率的平均

了解这个之后，整道题就清楚了，剩下就是处理两个小问题：

1）前W个位置概率的平均，如何记录，当然直接存下每一个，求和平均当然可以，但自己观察会发现，只用到了和的平均，那么用一个数来维护就够了，旧的删掉，新的加入（当然，如果到了K，就不能加入了）

2）最后题目要的，<=N的概率，其实就是，到达了[K，N]这一个区间的概率之和。

整个题目还是很好的！值得学习。