題目描述: 在第 1 天,一個人發現了一個秘密。每個知道秘密的人會在知道秘密 delay 天後開始向一個新人分享秘密,直到知道秘密 forget 天後忘記秘密。給定天數 n、delay 和 forget,求第 n 天有多少人知道秘密(對 10^9 + 7 取模)。
解題思路: 使用動態規劃。定義 dp[i] 為第 i 天「新知道秘密」的人數。第 1 天 dp[1] = 1。對於第 i 天,所有在第 j 天知道秘密(j 滿足 j + delay <= i 且 j + forget > i)的人都會在第 i 天分享秘密,因此 dp[i] = Σ dp[j],其中 max(1, i-forget+1) <= j <= i-delay。
最終答案為所有在第 n 天還記得秘密的人數,即 Σ dp[j],其中 j + forget > n(即 j > n - forget)。
可以用前綴和優化為 O(n)。
時間複雜度:O(n) — 一次遍歷加上滑動窗口
空間複雜度:O(n) — dp 陣列
1. Initialize dp[1] = 1, share = 0 2. For day i from 2 to n: a. If i - delay >= 1: share += dp[i - delay] (new sharers) b. If i - forget >= 1: share -= dp[i - forget] (people who forgot) c. dp[i] = share (new people learning secret today) 3. Sum dp[j] for all j where j + forget > n (people who still remember) 4. Return sum mod 10^9 + 7
差分陣列法:用差分陣列標記每個人從何時開始分享到何時停止。可以避免滑動窗口的邊界處理,但本質時間複雜度相同 O(n)。
矩陣快速冪法:將轉移方程寫成矩陣形式,使用矩陣快速冪將時間複雜度降至 O(forget^3 * log n)。當 n 很大但 forget 很小時有優勢。