leetcode-6109：知道秘密的人数

题目

题目连接
在第 1 天，有一个人发现了一个秘密。

给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 10^9 + 7 取余 后返回。

示例 1：

输入：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 。（五个人知道秘密）

示例 2：

输入：n = 4, delay = 1, forget = 3
输出：6
解释：
第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）
第 2 天：A 把秘密分享给 B 。（两个人知道秘密）
第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）
第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）

解题

方法一：模拟（超时）

建立两个队列来进行模拟

• 延时队列：已经知道秘密，但是还不能分享
• 分享队列：已经知道密码，并且可以进行分享

队列中存放的都是到期的日子，当延时队列中的元素到期，就会弹出并加入分享队列，分享队列中的元素到期，就会弹出，说明忘记了。

最后知道秘密的人，就是延时队列和分享队列中的总数

缺点：但是对于这道题来说，无需在乎知道秘密的人的是谁，题目场景简单，这种方法并不是最优，动态规划会更加合适。

class Solution {
    
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
    
        queue<int> q_delay;
        queue<int> q_shareing;
        q_delay.push(1+delay);
        for(int i=1;i<=n;i++){
    
            while(!q_delay.empty()&&i>=q_delay.front()){
    
                q_shareing.push(q_delay.front()+forget-delay);
                q_delay.pop();
            }
            while(!q_shareing.empty()&&i>=q_shareing.front()){
    
                q_shareing.pop();
            }
            for(int j=0;j<q_shareing.size();j++){
    
                q_delay.push(i+delay);
            }
        }
        return q_delay.size()+q_shareing.size();
    }
};

方法二：动态规划-刷表法

参考链接

根据题意，有两类人：

• A 类：知道秘密，但还不能分享；
• B 类：知道秘密，且可以分享。

dp[i]表示第i+1天，有dp[i]个B类人

特别要注意索引的细节，比如等号什么的。
对于if(i+delay>=n)，比如n=3,delay=2
第一天i=0，而i+delay=2,此时对于第n天来说，不能是算A类人的因为第二天就变成了B类人,因此要加上等号

另外dp[0]=1,并不符合dp的定义，只是为了初始化，方便后续计算。

class Solution {
    
public:
    const int MOD=1e9+7;
    int peopleAwareOfSecret(int n, int delay, int forget) {
    
        int cnt_a=0;
        vector<int> dp(n);//记录第i天的B类人
        dp[0]=1;
        for(int i=0;i<n;i++){
    
            if(i+delay>=n) cnt_a=(cnt_a+dp[i])%MOD;//第n天的A类人
            for(int j=i+delay;j<min(n,i+forget);j++){
    
                dp[j]=(dp[j]+dp[i])%MOD;
            }
        }
        return (cnt_a+dp[n-1])%MOD;//知道秘密的人=A类人+B类人
    }
};