920. Number of Music Playlists

class Solution {
    public int numMusicPlaylists(int n, int goal, int k) {
        long[][] dp = new long[goal + 1][n + 1];
        // dp[goal][1], dp[goal][2]
        int MOD = 1_000_000_007;
        dp[0][0] = 1;
        
        for (int i = 1; i <= goal; i++) {
            for (int j = 1; j <= n; j++) {
                // 1 out 3 songs, 2 options
                // j = 2, k = 3
                dp[i][j] += dp[i - 1][j - 1] * (n - j + 1);
                dp[i][j] += dp[i - 1][j] * Math.max(0, j - k);
                dp[i][j] %= MOD;
            }
        }
        return (int) dp[goal][n];
    }
}
                
class Solution {
    public int numMusicPlaylists(int n, int goal, int k) {
        long[] dp = new long[n + 1];
        // dp[goal][1], dp[goal][2]
        int MOD = 1_000_000_007;
        dp[0] = 1;

        for (int i = 1; i <= goal; i++) {
            for (int j = n; j > 0; j--) {
                // 1 out 3 songs, 2 options
                // j = 2, k = 3
                dp[j] = (dp[j - 1] * (n - j + 1) + dp[j] * Math.max(0, j - k)) % MOD;
            }
            dp[0] = 0;
        }

        return (int) dp[n];
    }
}