Number of People Aware of a Secret | Leetcode 2327

// C++: DP Tabulation
class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        int MOD = 1e9+7;
        vector<int> dp(n+1);
        dp[1] = 1;
        int win_count = 0;
        for(int curr=2;curr<=n;++curr){
            if(curr-delay > 0)
                win_count = (win_count + dp[curr-delay]) % MOD;
            if(curr-forget > 0)
                win_count = (win_count - dp[curr-forget] + MOD) % MOD;
            
            dp[curr] = win_count;
        }
        int total = 0;
        for(int i=n-forget+1;i<=n;++i)
            total = (total + dp[i]) % MOD;
        
        return total;
    }
};
/*
// C++: Recursion + Memoization: O(N^2)
class Solution {
    static const int MOD = 1e9+7;
    int MAX;
    vector<int> mem;

    int count(int curr, const int& delay, const int& forget) {
        if (mem[curr] != -1) return mem[curr];

        int total = (curr + forget - 1 >= MAX);
        for (int i = delay; i < forget; ++i) {
            if (curr + i > MAX) break;
            total = (total + count(curr + i, delay, forget)) % MOD;
        }
        return mem[curr] = total;
    }
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        MAX = n;
        mem.assign(n + 1, -1);
        return count(1, delay, forget);
    }
};
// JAVA: DP Tabulation
import java.util.*;

public class Solution {
    private static final int MOD = 1_000_000_007;
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        long[] dp = new long[n + 1];
        dp[1] = 1;
        long winCount = 0;

        for (int curr = 2; curr <= n; ++curr) {
            if (curr - delay > 0) {
                winCount = (winCount + dp[curr - delay]) % MOD;
            }
            if (curr - forget > 0) {
                winCount = (winCount - dp[curr - forget] + MOD) % MOD;
            }
            dp[curr] = winCount;
        }

        long total = 0;
        for (int i = Math.max(1, n - forget + 1); i <= n; ++i) {
            total = (total + dp[i]) % MOD;
        }
        return (int) total;
    }
}
// JAVA: Recursion + Memoization
import java.util.*;

public class Solution {
    private static final int MOD = 1_000_000_007;
    int MAX;
    int[] mem;

    private int count(int curr, int delay, int forget) {
        if (mem[curr] != -1) return mem[curr];
        long total = (curr + forget - 1 >= MAX) ? 1 : 0;
        for (int i = delay; i < forget; ++i) {
            if (curr + i > MAX) break;
            total = (total + count(curr + i, delay, forget)) % MOD;
        }
        mem[curr] = (int) total;
        return mem[curr];
    }

    public int peopleAwareOfSecret(int n, int delay, int forget) {
        MAX = n;
        mem = new int[n + 1];
        Arrays.fill(mem, -1);
        return count(1, delay, forget);
    }
}

# Python: DP Tabulation
class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (n + 1)
        dp[1] = 1
        win_count = 0

        for curr in range(2, n + 1):
            if curr - delay > 0:
                win_count = (win_count + dp[curr - delay]) % MOD
            if curr - forget > 0:
                win_count = (win_count - dp[curr - forget]) % MOD
            dp[curr] = win_count

        total = 0
        for i in range(max(1, n - forget + 1), n + 1):
            total = (total + dp[i]) % MOD

        return total

# Python: Recursion + Memoization
from functools import lru_cache

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        MOD = 10**9 + 7

        @lru_cache(None)
        def count(curr: int) -> int:
            total = 1 if curr + forget - 1 >= n else 0
            for i in range(delay, forget):
                if curr + i > n:
                    break
                total = (total + count(curr + i)) % MOD
            return total

        return count(1)
*/