LeetCode 6109. 知道秘密的人数

LeetCode 6109. 知道秘密的人数

线性DP + 前缀和优化

/* f[i][j]表示前i天，记得秘密j天的数量 j == 1: 一共有 delay <= j < forget数量 f[i][j] = f[i - 1][delay] + f[i - 1][delay + 1] ... f[i - 1][forget - 1]; 这里求了连续和，暴力n^3，会超时，前缀和优化 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;
    }
};