在第 1 天，有一个人发现了一个秘密，我来为大家科普一下关于leetcode数学题讲解?下面希望有你要的答案，我们一起来看看吧!
leetcode数学题讲解
6109. 知道秘密的人数题目（中等）在第 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/
,
