2022.07.03(LC_6109_知道秘密的人数)

 方法：动态规划

class Solution {
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        int MOD = 1000000007;
        //状态：f[i]表示第i天新知道秘密的人数
        int[] f = new int[n + 1];
        f[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                //在第i天，只有(i - forget, i - delay]这个区间里新知道秘密的人才会告诉其它人
                //注意i - forget + 1和 i - delay可能超出[1, n]的范围，需要处理一下边界
                if (j > i - forget && j <= i - delay) {
                    f[i] = (f[i] + f[j]) % MOD;
                }
            }
        } 
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            //答案就是在第n天还没有忘记秘密的人数之和
            if (i + forget > n) {
                ans = (ans + f[i]) % MOD;
            }
        }
        return ans;
    }
}