Skip to content

920. Number of Music Playlists 👍

Approach 1: Top-down

  • Time: $O(NL)$
  • Space: $O(NL)$
 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
28
29
class Solution {
 public:
  int numMusicPlaylists(int n, int goal, int k) {
    this->n = n;
    this->k = k;
    // dp[i][j] := # of playlists with i songs and j different songs
    dp.resize(goal + 1, vector<long>(n + 1, -1));
    return playlists(goal, n);
  }

 private:
  static constexpr int kMod = 1'000'000'007;
  int n;
  int k;
  vector<vector<long>> dp;

  long playlists(int i, int j) {
    if (i == 0)
      return j == 0;
    if (j == 0)
      return 0;
    if (dp[i][j] >= 0)
      return dp[i][j];

    dp[i][j] = playlists(i - 1, j - 1) * (n - (j - 1));  // Last song is new
    dp[i][j] += playlists(i - 1, j) * max(0, j - k);     // Last song is old
    return dp[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
26
27
28
class Solution {
  public int numMusicPlaylists(int n, int goal, int k) {
    this.n = n;
    this.k = k;
    // dp[i][j] := # of playlists with i songs and j different songs
    dp = new long[goal + 1][n + 1];
    Arrays.stream(dp).forEach(row -> Arrays.fill(row, -1));
    return (int) playlists(goal, n);
  }

  private static final int kMod = 1_000_000_007;
  private int n;
  private int k;
  private long[][] dp;

  private long playlists(int i, int j) {
    if (i == 0)
      return j == 0 ? 1 : 0;
    if (j == 0)
      return 0;
    if (dp[i][j] >= 0)
      return dp[i][j];

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

Approach 2: Bottom-up

  • Time: $O(NL)$
  • Space: $O(NL)$
 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] := # 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));  // Last song is new
        dp[i][j] += dp[i - 1][j] * max(0, j - k);      // 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] := # 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));  // Last song is new
        dp[i][j] += dp[i - 1][j] * Math.max(0, j - k); // Last song is old
        dp[i][j] %= kMod;
      }

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