LeetCode 6109. Number of people who know the secret

LeetCode 6109. Number of people who know the secret

linear DP + Prefixes and optimizations

/* f[i][j] Before presentation i God , Remember the secret j Number of days  j == 1:  Altogether  delay <= j < forget Number  f[i][j] = f[i - 1][delay] + f[i - 1][delay + 1] ... f[i - 1][forget - 1];  Here we find the continuous sum , violence n^3, Will timeout , Prefixes and optimizations  f[i][j] = f[i - 1][forget - 1] - f[i - 1][delay - 1]; j > 1: f[i][j] = f[i - 1][j - 1]; f[i][j] = f[i - 1][j - 1] - f[i - 1][j - 2] */
const int N = 1010, MOD = 1e9 + 7;
class Solution {
    
public:
    int f[N][N];
    int peopleAwareOfSecret(int n, int delay, int forget) {
    

        for(int i = 1; i <= forget; i ++) f[1][i] = 1;

        for(int i = 2; i <= n; i ++)
        {
    
            for(int j = 1; j <= forget; j ++)
            {
    
                if(j > 1) f[i][j] = (f[i - 1][j - 1] - f[i - 1][j - 2]) % MOD;
                else if(j == 1) f[i][j] = (f[i - 1][forget - 1] - f[i - 1][delay - 1]) % MOD;

                f[i][j] = (f[i][j] + f[i][j - 1]) % MOD;
            }
        }
        return (f[n][forget] + MOD) % MOD;
    }
};