题目

在第 1 天，有一个人发现了一个秘密。

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

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

示例 1：

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

示例 2：

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

提示：

  • 2 <= n <= 1000
  • 1 <= delay < forget <= n

    解题方法

    动态规划

    设定动态数组dp[i]表示第i天知道秘密的新人，则根据题意，该部分人是通过[i-forget, i-delay]这个区间内的人分享而产生的，因此有如下递推公式
    2327. 知道秘密的人数（300周赛） - 图1
    对于该公式，在递推的过程中会产生O(n^2)的时间复杂度，因此可以通过前缀和降低时间复杂度。设定新的动态数组dp'[i]表示从第1天到第i天所有知道秘密的新人的和。则对于上述递推公式可以改写如下：
    2327. 知道秘密的人数（300周赛） - 图2
    第n天时知道该秘密的人数即dp'[n]-dp'[n-forget]。
    时间复杂度O(n)，空间复杂度O(n)。
    C++代码：
    1. class Solution {
    2. public:
    3.   int peopleAwareOfSecret(int n, int delay, int forget) {
    4.       vector<int> s(n+1, 0);
    5.       s[1] = 1;
    6.       int mod = 1E9+7;
    7.       for(int i=2; i<=n; i++) {
    8.           s[i] = (s[i-1] + (s[max(0, i-delay)] - s[max(0, i-forget)] + mod) % mod ) % mod;
    9.       }
    10.       return (s[n]-s[max(0, n-forget)] + mod )%mod;
    11.   }
    12. };