题目

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

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

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 109 + 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 个新的人。（六个人知道秘密）

提示：

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

解题思路

一个累积问题加上了忘记的减去，可以维护三个数组，核心的公式是：第 i 天知道秘密的人数 = 第 i - 1 天知道秘密的人数 + 在第 i 天新知道秘密的人数 - 在第 i 天忘记秘密的人数。

代码如下：

class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {

        vector<int> nowKnow(n + 1 + forget, 0); // 记录第n天知道秘密的人数
        vector<int> delayKnow(n + 1 + forget, 0); // 记录第n天新知道秘密的人数
        vector<int> forgetKnow(n + 1 + forget, 0); // 记录第n天忘掉秘密的人数

        long long mod = 1e9 + 7;

        delayKnow[1] = 1; // 第1天一个人知道了

        for(int i = 1; i <= n; i++)
        {
            nowKnow[i] = ((1LL * nowKnow[i - 1] + delayKnow[i] - forgetKnow[i]) + mod) % mod; // 计算结果

            for(int j = i + delay; j < i + forget; j++) // 每个人的传播秘密生命周期
            {
                delayKnow[j] = (1LL * delayKnow[i] + delayKnow[j]) % mod; 
            }

            forgetKnow[i + forget] = delayKnow[i];
        }

        return nowKnow[n];
    }
};

这串代码需要注意：

为了保证结果始终为正，应该使用 (a - b % mod + mod) % mod 的技巧。
不能使用 delayKnow[j] += (1LL * delayKnow[i]) % MOD; 因为左侧 delayKnow[j] 本身累计可能早已很大，+= 后仍可能溢出 int。

优化思路

换一个角度思考。每天新增的知情人数，其实就等于当天能够分享秘密的总人数。

我们不需要为每个新人去遍历他未来会分享秘密的每一天。我们可以维护一个变量 sharing_count，表示“今天有多少人可以分享秘密”。

在第 i 天，有哪些人会开始分享秘密？
- 是那些在 i - delay 天前知道秘密的人。
在第 i 天，有哪些人会停止分享秘密？
- 是那些在 i - forget 天前知道秘密的人（因为他们今天忘记了）。

这样，我们就可以得到一个递推关系，所以这个问题就变成了一个更简单的DP规划问题：

我们可以只用一个DP数组。

设 dp[i] 为第 i 天新知道秘密的人数。

同时，我们维护一个变量 share，表示当天可以分享秘密的总人数。

状态定义: dp[i] 表示第 i 天新增的知情者数量。
初始化: dp[1] = 1。第1天有1个新人。
状态转移: 我们从第2天遍历到第 n 天。对于第 i 天：
- 更新可分享人数 share:
  - 今天，在 i - delay 天知道秘密的人（dp[i - delay]）开始有能力分享了，所以 share 增加 dp[i - delay]。
  - 今天，在 i - forget 天知道秘密的人（dp[i - forget]）忘记了秘密，失去了分享能力，所以 share 减少 dp[i - forget]。
- 计算今日新增人数 dp[i]:
  - 今天新增的人数就等于今天可以分享秘密的总人数，即 dp[i] = share。
最终结果: 第 n 天结束时，知道秘密的人是那些在 [n - forget + 1, n] 这个时间窗口内知道秘密的人的总和。因为更早知道秘密的人到第 n 天时已经忘记了。

优化代码

class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        long long mod = 1e9 + 7;
        
        // dp[i] 表示第 i 天新知道秘密的人数
        vector<long long> dp(n + 1, 0);
        
        // share 表示当前天可以分享秘密的总人数
        long long share = 0;
        
        // 第1天，有一个人知道了秘密
        dp[1] = 1;

        for (int i = 2; i <= n; ++i) {
            // 更新可以分享秘密的人数 share
            // 加上今天开始分享的 (i - delay 天知道的)
            // 减去今天忘记秘密的 (i - forget 天知道的)
            // 注意 i - delay 和 i - forget 可能 <= 0，需要判断
            if (i - delay > 0) {
                share = (share + dp[i - delay]) % mod;
            }
            if (i - forget > 0) {
                share = (share - dp[i - forget] + mod) % mod; // 防止负数
            }
            
            // 今天新增的人数 = 今天可以分享秘密的人数
            dp[i] = share;
        }

        // 计算第 n 天总共知道秘密的人数
        // 这些人是在 [n - forget + 1, n] 之间知道秘密的
        long long total_aware = 0;
        for (int i = n - forget + 1; i <= n; ++i) {
            total_aware = (total_aware + dp[i]) % mod;
        }
        
        return total_aware;
    }
};

2327. 知道秘密的人数

beautifulremi

题目

解题思路

优化思路

优化代码