Skip to content

920. Number of Music Playlists 👍

Approach 1: Top-down

  • Time: $O(n \cdot \texttt{goal})$
  • Space: $O(n \cdot \texttt{goal})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  int numMusicPlaylists(int n, int goal, int k) {
    vector<vector<long>> mem(goal + 1, vector<long>(n + 1, -1));
    return numMusicPlaylists(n, k, goal, n, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of playlists with i songs and j different songs.
  long numMusicPlaylists(int n, int k, int i, int j,
                         vector<vector<long>>& mem) {
    if (i == 0)
      return j == 0;
    if (j == 0)
      return 0;
    if (mem[i][j] >= 0)
      return mem[i][j];

    // The last song is new.
    mem[i][j] = numMusicPlaylists(n, k, i - 1, j - 1, mem) * (n - (j - 1));
    // The last song is old.
    mem[i][j] += numMusicPlaylists(n, k, i - 1, j, mem) * max(0, j - k);
    return mem[i][j] %= kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int numMusicPlaylists(int n, int goal, int k) {
    long[][] mem = new long[goal + 1][n + 1];
    Arrays.stream(mem).forEach(A -> Arrays.fill(A, -1));
    return (int) numMusicPlaylists(n, k, goal, n, mem);
  }

  private static final int kMod = 1_000_000_007;

  // Returns the number of playlists with i songs and j different songs.
  private long numMusicPlaylists(int n, int k, int i, int j, long[][] mem) {
    if (i == 0)
      return j == 0 ? 1 : 0;
    if (j == 0)
      return 0;
    if (mem[i][j] >= 0)
      return mem[i][j];

    // The last song is new.
    mem[i][j] = numMusicPlaylists(n, k, i - 1, j - 1, mem) * (n - (j - 1));
    // The last song is old.
    mem[i][j] += numMusicPlaylists(n, k, i - 1, j, mem) * Math.max(0, j - k);
    return mem[i][j] %= kMod;
  }
}

Approach 2: Bottom-up

  • Time: $O(n \cdot \texttt{goal})$
  • Space: $O(n \cdot \texttt{goal})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int numMusicPlaylists(int n, int goal, int k) {
    constexpr int kMod = 1'000'000'007;
    // dp[i][j] := the number of playlists with i songs and j different songs
    vector<vector<long>> dp(goal + 1, vector<long>(n + 1));
    dp[0][0] = 1;

    for (int i = 1; i <= goal; ++i)
      for (int j = 1; j <= n; ++j) {
        dp[i][j] += dp[i - 1][j - 1] * (n - (j - 1));  // The last song is new.
        dp[i][j] += dp[i - 1][j] * max(0, j - k);      // The last song is old.
        dp[i][j] %= kMod;
      }

    return dp[goal][n];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int numMusicPlaylists(int n, int goal, int k) {
    final int kMod = 1_000_000_007;
    // dp[i][j] := the number of playlists with i songs and j different songs
    long[][] dp = new long[goal + 1][n + 1];
    dp[0][0] = 1;

    for (int i = 1; i <= goal; ++i)
      for (int j = 1; j <= n; ++j) {
        dp[i][j] += dp[i - 1][j - 1] * (n - (j - 1));  // The last song is new.
        dp[i][j] += dp[i - 1][j] * Math.max(0, j - k); // The last song is old.
        dp[i][j] %= kMod;
      }

    return (int) dp[goal][n];
  }
}