力扣.300（一个比较隐蔽的dp）

6109. 知道秘密的人数
在第 1 天，有一个人发现了一个秘密。
给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。
同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。
一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。
给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。
由于答案可能会很大，请你将结果对 109 + 7 取余 后返回。

输入：n = 6, delay = 2, forget = 4
输出：5
解释：
第 1 天：假设第一个人叫 A 。（一个人知道秘密）
第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）

dp存当天新增的人数， 能传播秘密的区间累加 为当天新增的人数， 
当天总人数 为 没忘记秘密的区间累加
当天新增人数计算 为 i + delay 到 i + forget-1 的人数之和
当天所有人数 为 n-forget+1 到 n 的人数之和
需要注意的是，只需要关注累加即可，对于forget的，直接舍弃就可以
每天与之相关联的只有delay和forget之间的数据，符合dp的特征。

class Solution {
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        int mod = (int)1e9 + 7;
        // dp[i] 表示第i天新增的知道秘密的人数
        long[] dp = new long[n + 1];
        // 初始值，第一天有1个人知道
        dp[1] = 1;
        // 遍历n天,分别算出第i天在[i + delay, i + forget)区间内做出贡献的值并进行累加
        for(int i = 1; i < n + 1; i++){
            // 第i天的新增的人数能在下面这个for循环的区间内做出贡献
            for(int j = i + delay; j < i + forget && j < n + 1; j++){
                // 比如dp[3] += dp[1],说明第1天的人可以在第3天传播dp[1]个人
                dp[j] += dp[i];
                dp[j] %= mod;
            }
        }
        long ans = 0;
        // 只要计算出[n + 1 - forget, n + 1) 这个没有遗忘的人数和就是结果，
        // 比如说第6天知道秘密的人数就是 6 + 1 - forget(4),也就是从第3天开始累加人数就可以
        // 第3天之前的人都遗忘了
        for(int i = n + 1 - forget; i < n + 1; i++){
            ans += dp[i];
            ans %= mod;
        }
        return (int)ans;
    }
}