2327. Number of People Aware of a Secret

Leetcode link

题目简介

有个人在第一天的时候知晓了一个秘密，但是他只会在 delay 了几天后，才会把秘密告诉另外一个人（每人每天只能告诉一个人）

而且，每个人在得知消息的 forget 天后，就会忘了这个消息，在忘记消息的当天也无法再把秘密告诉其他人

题目要我们求在第 n 天的时候，这个秘密会有多少人知道

解题思路

根据题目，我们可以把所有的人分成两个部分：

• 当天刚得知秘密的人：我们用 dp[i] 代表在第 i 天有多少人刚刚得知秘密
• 当天能够分享秘密的人：我们用 share 来代表

根据题目描述，因为第一天只有一个人知道秘密，所以 dp[1] = 1，share = 0

从第二天开始，我们需要计算 share 跟 dp[i]

share 的计算有两个部分：

• 如果 $i - delay > 0$ ，share += dp[i - delay] ：这个等式表示，如果当前天数大于 delay 的天数之后，过了 delay 天数的那些人就可以开始分享秘密了
• 如果 $i-forget > 0$，share -= dp[i - forget]：这个等式表示，如果当前天数大于 forget 的天数之后，过了 forget 天数的那些人就不能分享秘密了

经过上述计算，我们可以得到当天可以 share 的人数

当天可以 share 的人数 = 当天新知道消息的人数，所以 dp[i] = share

综上，我们可以得知从第二天到第 n 天每天新得知消息的人数，那么我们要计算第 n 天还有多少人知道消息，我们只需要计算从第 n - forget + 1 天到第 n 天总共有多少人新得知消息就好，也就是 sum(dp[i]), i form (n-forget+1) to n

最后别忘了 mod 一个 $10^9+7$

Javascript

/**
 * @param {number} n
 * @param {number} delay
 * @param {number} forget
 * @return {number}
 */
var peopleAwareOfSecret = function (n, delay, forget) {
    const mod = 1000000007n
    const dp = new Array(n + 1).fill(0n)
    dp[1] = 1n
    // the number of people who can share on that day
    let share = 0n

    for (let i = 2; i <= n; i++) {
        if (i - delay > 0n) {
            share += dp[i - delay]
        }
        if (i - forget > 0) {
            share -= dp[i - forget]
        }
        dp[i] = share
    }

    let res = 0n
    for (let i = n - forget + 1; i <= n; i++) {
        res += dp[i]
    }

    return Number(res % mod)

};