知道秘密的人数

难度: Medium

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

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

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

Submission

运行时间: 23 ms

内存: 16.2 MB

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        dp = [1] + [0] * (n - 1)
        pre = dp[:]
        for j in range(1, n):
            if j >= forget:
                dp[j] = (pre[j - delay] - pre[j - forget])% (10 ** 9 + 7)
            else:
                dp[j] = pre[j - delay] % (10 ** 9 + 7)
            pre[j] = (pre[j - 1] + dp[j]) % (10 ** 9 + 7)

        if forget < n:
            res = (pre[-1] - pre[-forget - 1]) % (10 ** 9 + 7)
        else:
            res = pre[-1] % (10 ** 9 + 7)
        return res

Explain

本题使用动态规划方法来解决问题。定义dp[i]为第i天新知道秘密的人数。我们维护一个前缀和数组pre，其中pre[i]为直到第i天总共知道秘密的人数。对于每一天j，我们更新dp[j]为在第j-delay天知道秘密的人数减去第j-forget天知道秘密的人数（因为在第j-forget天的人在第j天已经忘记了秘密，不能再传播）。最后，根据forget的值来决定总的知道秘密的人数，如果forget小于n，则结果为pre[n-1]减去pre[n-forget-1]；否则，结果为pre[n-1]。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        dp = [1] + [0] * (n - 1)  # 初始化dp数组，第一天有一个人知道秘密
        pre = dp[:]  # 复制dp到pre作为前缀和数组的初始化
        for j in range(1, n):
            if j >= forget:
                # 从第j-delay天到第j-forget天的人数差是新知道秘密的人数
                dp[j] = (pre[j - delay] - pre[j - forget]) % (10 ** 9 + 7)
            else:
                # 在忘记秘密前，所有从第j-delay天开始的人都是新知道秘密的
                dp[j] = pre[j - delay] % (10 ** 9 + 7)
            # 更新前缀和数组
            pre[j] = (pre[j - 1] + dp[j]) % (10 ** 9 + 7)

        if forget < n:
            # 如果忘记时间小于总天数，计算剩余知道秘密的人数
            res = (pre[-1] - pre[-forget - 1]) % (10 ** 9 + 7)
        else:
            # 否则所有人都还记得秘密
            res = pre[-1] % (10 ** 9 + 7)
        return res

Explore

这种计算方法源于秘密传播和遗忘的规则。从第j-delay天知道秘密的人可以在第j天传播秘密，而从第j-forget天开始知道秘密的人到第j天已经忘记了秘密，不能再传播。因此，第j-delay天到第j-forget天之间的人数差代表了新能够传播秘密的人数。

当j小于forget时，意味着没有任何人会在第j天前忘记秘密，因此新知道秘密的人数就是从第j-delay天起的所有人。如果j-delay小于0，这实际上意味着在第1天之前没有人知道秘密，因此这部分人数应视为0。在实现中应通过条件判断来处理这种情况，以确保不会出现访问负索引的错误。

前缀和数组pre用于快速计算任意区间内的人数总和。通过直接使用dp数组的初始值来初始化pre，我们可以在更新dp数组时同步更新pre数组，从而在每一天都能准确地反映从第一天到当天总共知道秘密的人数。这样做是为了简化计算过程并减少错误的可能性。

如果delay或forget的值接近n，会影响算法的输出，特别是在计算最后几天的人数时。例如，如果forget值等于或大于n，则所有人在n天后仍记得秘密，这意味着我们只需返回最后的总人数。性能方面，这种情况可能减少了某些计算，因为对于大部分天数，忘记秘密的人数可能为零，简化了计算过程。然而，算法的时间复杂度总体上保持为O(n)，因为仍需遍历n天来更新dp和pre数组。