leetcode数学题讲解（LeetCode第300场周赛题解笔记）

在第 1 天，有一个人发现了一个秘密，我来为大家科普一下关于leetcode数学题讲解?下面希望有你要的答案，我们一起来看看吧!

leetcode数学题讲解

在第 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

设 f(i) 表示第 i 天新增知道秘密的人数。

状态转移：

根据题意，第 i 天能分享秘密的人为没忘记秘密并且知道秘密过了 delay 天的人，即 [i-forget 1,i-delay] 时间内的人，第 i 天新增的人数即为这段时间中的人数，因为这段时间的人会在第 i 天分享秘密给一个人。递推公式为：

初始化：f(1) = 1

题目要求第 n 天结束还知道秘密的人，答案为 [n-forget 1, n] 时间内新增的人数之和，即：

• 时间复杂度：。
• 空间复杂度：。

对于计算 [i-forget 1,i-delay] 时间内的人数，我们可以通过前缀和来优化，使时间复杂度降为 O(n)。

• 时间复杂度：。
• 空间复杂度：。

class Solution { public int peopleAwareOfSecret(int n, int delay, int forget) { final long MOD = 1000000007; long[] dp = new long[n 1]; dp[1] = 1; for (int i = 2; i <= n; i ) { for (int j = Math.max(i - forget 1, 1); j < i - delay; j ) { dp[i] = (dp[i] dp[j]) % MOD; } } long ans = 0; for (int i = n - forget 1; i <= n; i ) { ans = (ans dp[i]) % MOD; } return (int) ans; } }

class Solution { public int peopleAwareOfSecret(int n, int delay, int forget) { final long MOD = 1000000007; long[] sum = new long[n 1]; sum[1] = 1; for (int i = 2; i <= n; i ) { int l = Math.max(i - forget, 0); int r = Math.max(i - delay, 0); long f = (sum[r] - sum[l] MOD) % MOD; sum[i] = (sum[i - 1] f) % MOD; } return (int) ((sum[n] - sum[Math.max(n - forget, 0)] MOD) % MOD); } }

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