20220703 week race: number of people who know the secret - dynamic rules (problem solution)

Topic link ： Power button https://leetcode.cn/problems/number-of-people-aware-of-a-secret/

  Ideas ：

          At first, the idea was to have rabbits . The current number of people who know the secret = The number of people who knew the secret the day before +（i-delay） The number of people -（i-forget） The number of people . Later, in the process of derivation, it was found that ,(i-delay) People who , The first i The sky may not be still , It may have been forgotten .（i-forget） The number of people is also not allowed , Maybe （i-forget ——i） Have forgotten .

        Here's the thing ： The formula should be ： Number of people in the day = Number of people in the previous day -（ The first i Days forget the number ）+ Number of new people . that The first i Days forget the number and Number of new people How should I ask . In fact, just add an array get The array represents the number of new messages .

        Let's take an example .

         The first 1 The number of people receiving news from Tianxin is 1, namely get[1] = 1.

         The first 2 The number of people receiving news from Tianxin is 0（ Because it will take two days , To have the ability to publicize information ）, namely get[2] = 0.

         The first 3 The number of people receiving news from Tianxin is get[3] = get[3-2] = get[1] = 1.

        The first 4 The number of people receiving news from Tianxin is get[4] = get[4-2]+get[4-3] = get[2] +get[1] = 1.（ Because the people who got the propaganda news on the first day haven't forgotten , So you can still promote the news . We need to pay attention here . People in the past can't spread the news after they forget it .）

         therefore ： At present, the number of new people with information is ：

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

         therefore ： The first 5 The number of people receiving news from Tianxin is  ：get[5] = get[5-2] + get[5-3] = get[3]+get[2] = 1.( Because the first day of new information people , By the fifth day, he had no ability to spread news , And the first 4 Tianxin gets the news , It takes until the sixth day to have the ability to spread information .)

Let's look at our previous formula ： Number of people in the day = Number of people in the previous day -（ The first i Days forget the number ）+ Number of new people . We already know the number of new arrivals , So the first i How can I ask for the number of people I forget , Actually, the first one is i The number of people forgotten by heaven is get[i-forget]. So this problem has to be solved .

Code ：

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);
    }
}