Description

Submission

class Solution {
    const int M = 1e9 + 7;
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        vector<int> dp(n + 1);

        dp[1] = 1;
        for(int i = 1; i <= n; ++i) {
            for(int j = i + delay; j < i + forget; ++j) {
                if(j > n) break;
                dp[j] = (dp[j] + dp[i]) % M;
            }
        }

        int ret = 0;
        for(int i = 1; i <= n; ++i) {
            if(i + forget > n) ret = (ret + dp[i]) % M;
        }

        return ret;
    }
};


// dp[i]: how many new people know the secret on i-th decay


// for(int j = i + delay; j < i + forget; ++j) {
//     if(j >= n) break;
//     dp[j] = (dp[j] + dp[i]) % M;
// }