2327. 知道秘密的人数(递推)

2327. 知道秘密的人数(递推)

一维dp就可以qwq。令$f_i$表示第$i$天新知道秘密的人数。

第$i$天可以由$(i-forget,i-delay]$ 递推。

显然可以预处理前缀和，做到$O(n)$

最后的答案就是：$\sum _{i=n-forget+1}^n{f}_i$

class Solution {
    
    const int MOD = 1000000007;

public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
    
        vector<long long> f(n + 1), g(n + 1);
        f[1] = g[1] = 1;
        for (int i = 2; i <= n; i++) {
    
            int L = max(0, i - forget);
            int R = max(0, i - delay);
            f[i] = (g[R] - g[L] + MOD) % MOD;
            g[i] = (g[i - 1] + f[i]) % MOD;
        }
        return (g[n] - g[max(0, n - forget)] + MOD) % MOD;
    }
};