20220703 周赛：知道秘密的人数-动规（题解）

题目链接：力扣https://leetcode.cn/problems/number-of-people-aware-of-a-secret/

 思路：

         一开始的思路是生兔子。当前知道秘密的人数=前一天知道秘密的人数+（i-delay）的人数-（i-forget）的人数。后来推导的过程中发现，(i-delay)的人，第i天不一定还在，说不定已经遗忘了。（i-forget）的人数也是不准的，说不定在（i-forget ——i）之间已经遗忘了。

        问题的关键是：得到的式子应该是：当天人数 = 前一天人数-（第i天忘记的人数）+ 新得到消息的人数。那么第i天忘记的人数和新得到消息的人数应该怎么求呢。其实只要添加一个数组get数组表示新得到消息的人数就可以。

        我们以示例来看一下。

        第1天新得到消息的人数为1，即get[1] = 1。

        第2天新得到消息的人数为0（因为需要两天后，才具备宣传消息的能力），即get[2] = 0。

        第3天新得到消息的人数为get[3] = get[3-2] = get[1] = 1。

        第4天新得到消息的人数为get[4] = get[4-2]+get[4-3] = get[2] +get[1] = 1.（因为第一天新得到宣传消息的人还没有忘记，所以仍可以宣传消息。这里就要注意了。之前的人忘记消息以后就不能传播了。）

        所以：当前新具备得到消息的人数为：

for(int k = i-forgrt+1; k <= i-delay; k++) {
    get[i] += get[k]
}

        所以：第5天新得到消息的人数为 ：get[5] = get[5-2] + get[5-3] = get[3]+get[2] = 1.(因为第一天新得到消息的人，到第五天已经不具备传播消息的能力了，而第4天新得到消息的人，要到第六天才能具备传播消息的能力。)

再来看我们之前的公式：当天人数 = 前一天人数-（第i天忘记的人数）+ 新得到消息的人数。新的到消息的人数我们已经知道了，那么第i天忘记的人数怎么求呢，其实第i天忘记的人数就是get[i-forget]。于是此题得解。

代码：

class Solution {
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        long init = 0;
        long[] get = new long[n+1];
        long all = 0;
        init = 0;
        get[1] = 1;
        all = 1;
        for(int i = 2; i<=n; i++) {
            if(i-forget >= 1) {
                all = all+1000000007;
                init = (all - get[i-forget])%1000000007;
                // System.out.println("init"+i+":"+init[i]);
            } else {
                init = all;
                // System.out.println("init"+i+":"+init[i]);
            }
            for(int k = i-forget+1;k<=(i-delay);k++) {
                if(k >= 1) {
                    get[i] +=get[k];
                    get[i] %=  1000000007;
                     // System.out.println("get"+i+":"+get[i]);
                }
            }
            all = (init + get[i]) % 1000000007;
            // System.out.println(i+":"+all[i]);
        }
        return (int)(all % 1000000007);
    }
}