https://leetcode.com/problems/number-of-people-aware-of-a-secret/
DP再次教我做人。
这道题根本想不到用DP做，看到hint1的DP，瞬间恍然大悟。DP问题的难点在于，如何构造DP对象，这道题是个很好的例子。

个人解答

  1. const MOD = 1000000007
  3. func peopleAwareOfSecret(n int, delay int, forget int) int {
  4.     dp := make([]int, forget)
  5.     dp[0] = 1
  7.     for i := 2; i <= n; i++ {
  8.         for j := forget - 1; j > 0; j-- {
  9.             dp[j] = dp[j - 1]
  10.         }
  12.         dp[0] = 0
  13.         for j := delay; j < forget; j++ {
  14.             dp[0] += dp[j]
  15.             dp[0] %= MOD
  16.         }
  17.     }
  19.     res := 0
  20.     for i := 0; i < forget; i++ {
  21.         res += dp[i]
  22.         res %= MOD
  23.     }
  25.     return res
  26. }

题目分析

这道题是个很实际的问题，抽象的也很好，是个好题。乍一看，似乎是个找规律的题目，从传播中找到一个固定的模式，然后用一个通用的公式求出第n天的结果。不过，死活想不出来。
再想想，新的一天知道的人，依赖这一天可以传播的所有人，这一天已经知道的所有人，就是所有已知且还没有忘了的人。这种递推关系，有点DP的影子了。
然后想DP的对象和状态转移方程，最直白的，dp[i]表示第i天知道的所有人，但是这个信息不够，无法记录新增多少人，忘了多少人。考虑加一个信息：dp[i][j]表示第i天已经知道了j天的人。如果能这么想到，推出递推公式比较直观了。

  1. dp[i][j] = dp[i - 1][j - 1] // for j > 1
  2. dp[i][j] = sum(dp[i][delay...forget]) // for j = 0

j = 0表示刚知道，刚知道的人，也就是这一天能传播的人，也就是知道天数在[delay, forget) 区间的人了。
最后把所有第n天知道的人sum一下就好了，具体的看代码。