知道秘密的人数 图解题解

这道题到底在问什么

输入

n=6, delay=2, forget=4

输出

5

输入

n=4, delay=1, forget=3

输出

6

最优解：一步一步想明白

1. 3记住两句：新学会 dp[i] = 窗口 [i-forget+1, i-delay] 的新增之和；最终答案 = 最近 forget 天新学会的人数之和。下面每帧都在套它。
2. 4开局：第 1 天有 1 个人知道秘密，所以 dp[1]=1（绿色）。下标 0 是占位守卫(灰)，恒为 0。从第 2 天起，每天的新增都要靠前面几天推出来。
3. 5推 第 2 天 的新增 dp[2]。窗口 [-1, 0] 整个落在第 1 天之前，还没有人到了能分享的日子，所以今天没有新学会的人。
4. 6把结果填进去：dp[2]=0(绿色)。这一格从此定死，作为后面更晚那些天的贡献来源。
5. 7推 第 3 天 的新增 dp[3]。能在今天教新人的，是学会日落在第 1 到 1 天(黄框)的人：更早的已经忘、更晚的还没到分享日。
6. 8把黄框里这几天的新增加起来：dp[1]=1，一共 1 人。也就是说 第 3 天 会新学会 1 个人。
7. 9把结果填进去：dp[3]=1(绿色)。这一格从此定死，作为后面更晚那些天的贡献来源。
8. 10推 第 4 天 的新增 dp[4]。能在今天教新人的，是学会日落在第 1 到 2 天(黄框)的人：更早的已经忘、更晚的还没到分享日。
9. 11把黄框里这几天的新增加起来：dp[1]=1，dp[2]=0，一共 1 人。也就是说 第 4 天 会新学会 1 个人。
10. 12把结果填进去：dp[4]=1(绿色)。这一格从此定死，作为后面更晚那些天的贡献来源。
11. 13推 第 5 天 的新增 dp[5]。能在今天教新人的，是学会日落在第 2 到 3 天(黄框)的人：更早的已经忘、更晚的还没到分享日。
12. 14把黄框里这几天的新增加起来：dp[2]=0，dp[3]=1，一共 1 人。也就是说 第 5 天 会新学会 1 个人。
13. 15把结果填进去：dp[5]=1(绿色)。这一格从此定死，作为后面更晚那些天的贡献来源。
14. 16推 第 6 天 的新增 dp[6]。能在今天教新人的，是学会日落在第 3 到 4 天(黄框)的人：更早的已经忘、更晚的还没到分享日。
15. 17把黄框里这几天的新增加起来：dp[3]=1，dp[4]=1，一共 2 人。也就是说 第 6 天 会新学会 2 个人。
16. 18把结果填进去：dp[6]=2(绿色)。这一格从此定死，作为后面更晚那些天的贡献来源。
17. 19到这里，1 到 6 天每天新学会多少人都推完了。但注意 dp 是「当天新学会」的人数，不是总人数。第 6 天还知道秘密的，只有最近 forget=4 天里学会、还没忘的人。
18. 20第 6 天结束时，只有第 3 到 6 天(黄框)学会的人还没忘、仍知道秘密。更早学会的(第 1、2 天)满 forget 天已经忘了。把黄框里的 dp 加起来即答案。
19. 21加上第 3 天新学会的 dp[3]=1 人，running 小计到 1。绿色是已经数进答案的天。
20. 22加上第 4 天新学会的 dp[4]=1 人，running 小计到 2。绿色是已经数进答案的天。
21. 23加上第 5 天新学会的 dp[5]=1 人，running 小计到 3。绿色是已经数进答案的天。
22. 24加上第 6 天新学会的 dp[6]=2 人，running 小计到 5。绿色是已经数进答案的天。
23. 25最近 4 天学会的人加满，一共 5 人，这就是第 6 天知道秘密的总人数，答案 5。和题面示例 1 的 5 完全对上。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        m = (n << 1) + 10
        d = [0] * m
        cnt = [0] * m
        cnt[1] = 1
        for i in range(1, n + 1):
            if cnt[i]:
                d[i] += cnt[i]
                d[i + forget] -= cnt[i]
                nxt = i + delay
                while nxt < i + forget:
                    cnt[nxt] += cnt[i]
                    nxt += 1
        mod = 10**9 + 7
        return sum(d[: n + 1]) % mod

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        const int mod = 1e9 + 7;
        int m = (n << 1) + 10;
        vector<long long> d(m), cnt(m);
        cnt[1] = 1;
        for (int i = 1; i <= n; i++) {
            if (cnt[i]) {
                d[i] = (d[i] + cnt[i]) % mod;
                d[i + forget] = (d[i + forget] - cnt[i] + mod) % mod;
                int nxt = i + delay;
                while (nxt < i + forget) {
                    cnt[nxt] = (cnt[nxt] + cnt[i]) % mod;
                    nxt++;
                }
            }
        }
        long long ans = 0;
        for (int i = 0; i <= n; i++) {
            ans += d[i];
        }
        return ans % mod;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        final int mod = (int) 1e9 + 7;
        int m = (n << 1) + 10;
        long[] d = new long[m];
        long[] cnt = new long[m];
        cnt[1] = 1;
        for (int i = 1; i <= n; ++i) {
            if (cnt[i] > 0) {
                d[i] = (d[i] + cnt[i]) % mod;
                d[i + forget] = (d[i + forget] - cnt[i] + mod) % mod;
                int nxt = i + delay;
                while (nxt < i + forget) {
                    cnt[nxt] = (cnt[nxt] + cnt[i]) % mod;
                    ++nxt;
                }
            }
        }
        long ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans = (ans + d[i]) % mod;
        }
        return (int) ans;
    }
}

复杂度

面试官可能追问