6109. 知道秘密的人数

Difficulty
Medium
Tags
动态规划
URL
https://leetcode.cn/problems/number-of-people-aware-of-a-secret/
Star
在第 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 个新的人。（六个人知道秘密）
提示：
  • 2 <= n <= 1000
  • 1 <= delay < forget <= n

动态规划

思路
斐波那契数列问题的进阶版。
先来看一下朴素的斐波那契数列问题：给定整数 N，返回斐波那契数列的第N 项， 定义f(n)=f(n-1)+f(n-2)
再来看一下上台阶问题：给定整数N，代表台阶数，一次可以跨2 个或者1 个台阶，返回有多少种走 法。
如果台阶只有1 级，方法只有1 种。如果台阶有2 级，方法有2 种。如果台阶有N 级，最后跳上第N 级的情况，要么是从N-2 级台阶直接跨2 级台阶，要么是从N-1 级台阶跨1 级台阶，所以台阶有N 级的方法数为跨到N-2 级台阶的方法数加上跨到N-1 级台阶的方法数，即S(N)=S(N-1)+S(N-2)，初始项S(1)==1，S(2)==2。
再来看一下母牛生小牛问题：假设农场中的牛从3岁之后每年会生1 头小母牛，并且永远不会死。第一年农场有1 只的母牛，从第二年开始，母牛开始生小母牛。每只小母牛3 年之后又可以生 小母牛。给定整数N，求出N 年后牛的数量。
所有的牛都不会死，所以第N-1年的牛会毫无损失地活到第N 年。同时所有大于等于3岁的牛都会生1 头新的牛，那么大于等于3岁的牛的数量如何估计？就是第N-3 年的所有牛，到第N 年肯定都是大于3岁的牛。所以C(n)=C(n-1)+C(n-3)，初始项为C(1)==1，C(2)==2，C(3)==3。
再看一道母牛生小牛的问题：母牛从3-7岁初每年会生产1头母牛，10岁后死亡（10岁仍然存活）。假设初始有1头刚出生的母牛，请问第n年有多少头母牛？（年从第一年开始计数）
今年的母牛数=上年的母牛数 + 今年新出生的小牛数，而今年出生的小牛数就是年龄在3-7岁之间的母牛数，这个数是怎计算的呢，这个是有区分的：
1、当n < 8的时候，所有的牛的年龄都不超过7岁的，今年新出生的小牛数就是两年前的母牛数，因为两年前的母牛，在今年时，年龄都在3-7岁之间；
2、当n >= 8时，就出现了另外一个问题，有的母牛年龄超过7了，无法生产了故dp[i-2]里面包含了一些无法生产的母牛，要从中扣除，是哪些母牛无法生产了呢，那就是7年前的全部母牛，
eg：当n=8时，就是第一年的所有母牛无法生产，因为他们已经8岁了在dp计算的过程中，我们只是考虑了能不能生产的问题，我们并没有考虑死亡的问题，为啥没考虑呢，因为死亡的问题在过程中计算很麻烦的，eg:n=13的时候，要扣除n=3那年的母牛数， n=12的时候要扣除n=2那年的母牛数但是n=3的母牛数是包含n=2的母牛数的，所以不能是简单减去dp[i-10],这样会造成重复扣除，最简单的办法是在过程中不去减去死亡的母牛数，我们当他们一直活着，之所以能这么做，是因为超过7岁就不能生产了，他们自只代表自己，不会在生小牛，所以在中间扣除和最后扣除效果是一样的，因此，我们在最后的时候，扣除10年前的母牛数即可，
如果母牛死之前一直都可以生小牛，那就必须在过程中扣除死亡的母牛数，要是不扣除，母牛就会一直生小牛，在最后只扣除10年前的母牛数就是错误的，因为延迟扣除，他们又生了若干小牛，这些小牛是不应改存在的。
notion imagenotion image
本题中知道秘密的人会忘记，类比母牛生小牛问题中，母牛会死。
今天知道秘密的人数=昨天知道的人数 + 今天新知道的人数。
正常情况下：今天新知道的人数 = 今天能分享的人数， 即dp[i-delay]，但是会存在遗忘的情况，即并不是每个人超过了delay天 就能分享，还要减去遗忘的人数，因此： 今天新知道的人数 = dp[i-delay] - dp[i-forget]。
综上：
dp[i] = dp[i-1] + dp[i-delay] - dp[i-forget]。
最后，还需要剪掉遗忘的人数 res = dp[n] - dp[n-forget]
题解
class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        if n <= 1:
            return n
        
        dp = [0] * (n+1)
        dp[0] = 0
        dp[1] = 1
        
        for i in range(2, n+1):
            if i <= forget:
                dp[i] = dp[i-1] + dp[i-delay] if i-delay >= 0 else dp[i-1]
            else:
                dp[i] = dp[i-1] + dp[i-delay] - dp[i-forget]
        
        
        if i > forget:
            return (dp[-1] - dp[i-forget]) % (10**9 + 7)
        return dp[n] % (10**9 + 7)

法2 动态规划

思路
定义状态：dp[i]:为第 i 天 新知道秘密的人数，那么最终答案就是 sum(dp[n-forget:])
对于第i天而言，只有第i-forget+1到第i-delay之间新知道秘密的人，才会在这天把秘密告诉给一个新人，因为i-forget天以前知道秘密的已经忘掉了，而i-delay+1天以后知道秘密的，在第i天还处于冷冻期，无法传播秘密，因此dp[i]=sum(dp[i-forget+1:i-delay+1])，
可以用滑窗来维护这个区间和，最终时间复杂度为O(n)
题解
class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        prefix = [0] * (n+1)
        dp = [0] * (n+1)

        prefix[1] = 1
        dp[1] = 1
        
        for i in range(2, n+1):
            l = max(0, i-forget)
            r = max(0, i-delay)

            dp[i] = prefix[r] - prefix[l]
            prefix[i] = prefix[i-1] + dp[i]

        return (prefix[n] - prefix[max(0, n-forget)]) % (10 ** 9 + 7)