题目
在第 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类人 } };
