Number of Music Playlists LeetCode solution in C++

1
class Solution {
2
 public:
3
  using ll = long long;
4
  int N, target;
5
  int dp[102][102];
6
  int mod = 1e9 + 7;
7
  ll solve(int unique, int taken, int k) {
8
    if (unique > N || (taken == target && unique < N)) return 0;
9
    if (taken == target) return 1;
10

11
    int ans = 0;
12

13
    if (dp[unique][taken] != -1) return dp[unique][taken];
14

15
    // first time adding a new song
16
    ans = (solve(unique + 1, taken + 1, k) * (N - unique)) % mod;
17

18
    // repeat from already chosen songs
19
    int val = solve(unique, taken + 1, k) * max(0, unique - k) % mod;
20
    ans += val;
21

22
    ans %= mod;
23
    return dp[unique][taken] = ans;
24
  }
25

26
  int numMusicPlaylists(int n, int goal, int k) {
27
    memset(dp, -1, sizeof(dp));
28
    N = n, target = goal;
29
    return solve(0, 0, k);
30
  }
31
};