主題
題目連結：
題目意譯：
第一天，有一個人發現了一個秘密。
你被給定一整數 delay，其代表著每個人從發現秘密開始算起 delay 天後每一天都會分享該秘密給新的人。你同時也被給定一整數 forget，其代表著每個人會在得知秘密後開始算起 forget 天後忘記該秘密本身。任何人都沒辦法在忘記秘密的那一天以及之後的每一天分享秘密給別人。
給定一整數 n，回傳在第 n 天結束時知道秘密的人數。由於答案可能很大，將其模 10 ^ 9 + 7 後再回傳。
限制：
2 ≦ n ≦ 1000
1 ≦ delay < forget ≦ n
範例測資：
範例 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 各自分享秘密給一個新的人，叫做 C 和 D。（4 個人）
第 4 天：A 忘記了秘密，而 B 、 C 和 D 分享秘密給三個新的人。（6 個人）
解題思維：
經典的動態規劃（Dynamic Programming，DP）題型。
定義一陣列 D，其中 D[i] 代表在第 i 天結束時總計有多少人「現在」或「曾經」知道秘密。
根據題意，停止條件就是單純的 D[1] = 1；而遞迴式則為
D[i] = D[i - 1]，如果 i < delay；
D[i] = D[i - 1] + D[i - delay]，如果 delay ≦ i < forget；
D[i] = D[i - 1] + D[i - delay] - D[i - forget]，如果 forget ≦ i。
遞迴式第一條很顯然，前 delay - 1 天第一個人傳不了秘密；而第二條也很單純，就是位於現在這一天 delay 天前的曾經或現在知道的秘密的人將會傳給新的人，而因為天數還未及 forget，所以尚未有人忘記秘密；而最後的第三條就是單純地新把所有人都當作還記得秘密然後會傳給新的人，然後減去那些忘記的人即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
