---
# System prepended metadata

title: 2327. Number of People Aware of a Secret
tags: [Leetcode, Dynamic Programming, Medium]

---

# 2327. Number of People Aware of a Secret
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/number-of-people-aware-of-a-secret/description/
## 思路
思路[参考](https://leetcode.com/problems/number-of-people-aware-of-a-secret/solutions/2229982/java-c-python-sliding-window-o-n-time-o-forget-space/)
难点在于如何定义dp[i]
dp[i]表示在第i天发现secret的人
share表示当下有多少人可以share secret
## Code
### DP $O(n)$ $O(n)$ 
```java=
class Solution {
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        long[] dp = new long[n+1];
        dp[1] = 1;
        long share = 0;
        int mod = 1000000007;
        for(int i=2; i<=n; i++){
            share = (share+dp[Math.max(i-delay, 0)]-dp[Math.max(i-forget, 0)]+mod)%mod;
            dp[i] = share;
        }
        long ans = 0;
        for(int i=n-forget+1; i<=n; i++){
            ans = (ans+dp[i])%mod;
        }
        return (int)ans;
    }
}
```
### Rolling DP $O(n)$ $O(forget)$
```java=
class Solution {
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        long[] dp = new long[forget];
        dp[1] = 1;
        long share = 0;
        int mod = 1000000007;
        for(int i=2; i<=n; i++){
            share = (share+dp[(i-delay+forget)%forget]-dp[i%forget]+mod)%mod;
            dp[i%forget] = share;
        }
        long ans = 0;
        for(int i=n-forget+1; i<=n; i++){
            ans = (ans+dp[i%forget])%mod;
        }
        return (int)ans;
    }
}
```