Medium

题目描述

在第 1 天，有一个人发现了一个秘密。

给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新人分享秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会忘记这个秘密。一个人不能在忘记秘密那一天（或者之后的日子）分享秘密。

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 10^9 + 7 取余 后返回。

示例 1：

输入：n = 6, delay = 2, forget = 4
输出：5
解释：
第 1 天：假设第一个人叫 A。(1 人)
第 2 天：A 是唯一一个知道秘密的人。(1 人)
第 3 天：A 将秘密分享给 B。(2 人)
第 4 天：A 将秘密分享给 C。(3 人)
第 5 天：A 忘记了秘密，B 将秘密分享给 D。(3 人)
第 6 天：B 将秘密分享给 E，C 将秘密分享给 F。(5 人)

示例 2：

输入：n = 4, delay = 1, forget = 3
输出：6
解释：
第 1 天：第一个人叫 A。(1 人)
第 2 天：A 将秘密分享给 B。(2 人)
第 3 天：A 和 B 将秘密分享给 2 个新人 C 和 D。(4 人)
第 4 天：A 忘记了秘密。B，C 和 D 将秘密分享给 3 个新人。(6 人)

提示：

  • 2 <= n <= 1000
  • 1 <= delay < forget <= n

解题思路

这是一个典型的动态规划问题，需要追踪每一天知道秘密的人数以及他们的状态。

核心思路：

  1. 状态定义：用 dp[i][j] 表示第 i 天，已经知道秘密 j+1 天的人数
  2. 状态转移：
    • 如果 j > 0，那么 dp[i][j] = dp[i-1][j-1]（昨天知道 j 天的人，今天就知道 j+1 天）
    • dp[i][0] 表示第 i 天新知道秘密的人数，等于所有能分享秘密的人数之和
  3. 分享条件：一个人在知道秘密的第 delay 天到第 forget-1 天之间可以分享秘密

关键观察：

  • 知道秘密 delay 到 forget-1 天的人可以分享秘密
  • 知道秘密 forget 天及以上的人会忘记秘密
  • 每个能分享的人每天分享给一个新人

优化思路： 可以用一维数组 dp[j] 表示当前天知道秘密 j+1 天的人数，从后往前更新避免重复计算。同时维护能分享秘密的总人数，避免重复求和。

推荐解法： 使用一维DP优化的方法，时间和空间复杂度都更优。

代码实现

class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        const int MOD = 1e9 + 7;
        vector<long long> dp(forget, 0);
        dp[0] = 1;  // 第1天有1个人知道秘密1天
        
        for (int i = 2; i <= n; i++) {
            long long newPeople = 0;
            // 计算能分享秘密的人数
            for (int j = delay - 1; j < forget - 1; j++) {
                newPeople = (newPeople + dp[j]) % MOD;
            }
            
            // 更新dp数组，从后往前避免覆盖
            for (int j = forget - 1; j > 0; j--) {
                dp[j] = dp[j - 1];
            }
            dp[0] = newPeople;
        }
        
        long long result = 0;
        for (int j = 0; j < forget; j++) {
            result = (result + dp[j]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * forget
        dp[0] = 1  # 第1天有1个人知道秘密1天
        
        for i in range(2, n + 1):
            # 计算能分享秘密的人数
            new_people = sum(dp[delay-1:forget-1]) % MOD
            
            # 更新dp数组，从后往前避免覆盖
            for j in range(forget - 1, 0, -1):
                dp[j] = dp[j - 1]
            dp[0] = new_people
        
        return sum(dp) % MOD

public class Solution {
    public int PeopleAwareOfSecret(int n, int delay, int forget) {
        const int MOD = 1000000007;
        long[] dp = new long[forget];
        dp[0] = 1;  // 第1天有1个人知道秘密1天
        
        for (int i = 2; i <= n; i++) {
            long newPeople = 0;
            // 计算能分享秘密的人数
            for (int j = delay - 1; j < forget - 1; j++) {
                newPeople = (newPeople + dp[j]) % MOD;
            }
            
            // 更新dp数组，从后往前避免覆盖
            for (int j = forget - 1; j > 0; j--) {
                dp[j] = dp[j - 1];
            }
            dp[0] = newPeople;
        }
        
        long result = 0;
        for (int j = 0; j < forget; j++) {
            result = (result + dp[j]) % MOD;
        }
        
        return (int)result;
    }
}

var peopleAwareOfSecret = function(n, delay, forget) {
    const MOD = 1e9 + 7;
    const dp = new Array(forget).fill(0);
    dp[0] = 1;  // 第1天有1个人知道秘密1天
    
    for (let i = 2; i <= n; i++) {
        let newPeople = 0;
        // 计算能分享秘密的人数
        for (let j = delay - 1; j < forget - 1; j++) {
            newPeople = (newPeople + dp[j]) % MOD;
        }
        
        // 更新dp数组，从后往前避免覆盖
        for (let j = forget - 1; j > 0; j--) {
            dp[j] = dp[j - 1];
        }
        dp[0] = newPeople;
    }
    
    let result = 0;
    for (let j = 0; j < forget; j++) {
        result = (result + dp[j]) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n × forget)需要遍历 n 天，每天处理 forget 个状态
空间复杂度O(forget)使用一维数组存储状态