Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

920. Number of Music Playlists

Time: $O(NL)$

Space: $O(NL)$

			


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:
  constexpr static 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;
  }
};




			


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;
  }
}




			


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];
  }
};