【算法笔记】记一道力扣周赛：知道秘密的人

题目链接：https://leetcode.cn/problems/number-of-people-aware-of-a-secret/

三个输入，n，delay，forget，从第一天开始有1个人知道秘密，delay天之后他会每天告诉一个人秘密，直到forget天，之后他就忘掉了秘密不会再告诉别人了，然后其他人会继续告诉秘密。求第n天知道秘密的总人数。

这道题很明显的dp问题。有个最直观的想法是，今天新人数i，在delay到forget时间段会每天+i个知道秘密的人。也就是某一天新增的人数，只会影响之后的某一个时间段[delay, forget)内的人数变动。

 for i in range(1, n+1): #当天新增n人，+delay-forget每天就会新增dp[i]人
      for j in range(i+delay, min(i+forget, n+1)):
          dp[j] += dp[i]
1
2
3

但如果这时候你开始尝试去表示每一天到底有多少人知道秘密，这题就会变得很难了。。

换个角度，无论每天知道秘密多少人，在达到forget的时间后都会忘记，唯一不会忘记的人，或者说还没来得及忘记的，就是最后那几天的人，也就是i+forget>n的那一群人。于是最后那几天新增的人数的总和，就是最后的答案。而新增的人数是很好求的，他只和他之前的dp[i]有关。

全部代码：

import numpy as np
class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
            dp = [np.long(0) for i in range(n+1)]

            dp[1] = np.long(1)

            for i in range(1, n+1): #当天新增n人，+delay-forget每天就会新增dp[i]人
                for j in range(i+delay, min(i+forget, n+1)):
                    dp[j] += dp[i]

            res = np.long(0)
            for i in range(n- forget + 1, n+1):
                res+=dp[i]

            return res%np.long(1e9 + 7)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16