[LeetCode]Number of Music Playlists

DP的题目，我么需要稍微思考一下如何表示子问题。比较好的做法用dp[i][j]表示长度为i的playlist并且有j个unique song的情况下，总的可能数。那么在选择位于i位置的歌曲的时候，我们只有两种选择：

• 选择一首之前没有播放过的歌曲，这样情况下的方法数为dp[i - 1][j - 1] * (N - j + 1)
• 选择一手之前播放过了的歌，i前面的k首歌肯定是不能选的，因为这k首歌肯定是没有重复的，所以我们还有(j - K)首歌曲可以选。方法数为dp[i - 1][j] * (j - K)
• 这样dp[i][j] = dp[i - 1][j - 1] * (N - j + 1) + dp[i - 1][j] * (j - K)

时间复杂度O(N * L)，空间复杂度O(N * L)。代码如下：

	class Solution {
	public:
	int numMusicPlaylists(int N, int L, int K) {
	const int MOD = 1000000007;
	//dp[i][j] represents # of ways we can create playlist with
	//length i and j unique songs, the result is dp[L][N]
	//dp[i][j] = dp[i - 1][j - 1] * (N - j + 1) + dp[i - 1][j] * (j - K)
	//dp[i - 1][j - 1] * (N - j + 1) is # of ways we pick a unique song at i
	//dp[i - 1][j] * (j - K) is # of way we pick a repeated song at i
	vector<vector<long>> dp(L + 1, vector<long>(N + 1, 0));
	dp[1][1] = N;
	for (int i = 2; i <= L; ++i)
	{
	for (int j = 1; j <= min(i, N); ++j)
	{
	dp[i][j] = (dp[i - 1][j - 1] * (N - j + 1)) % MOD;
	if (j >= K)dp[i][j] += dp[i - 1][j] * (j - K);
	dp[i][j] %= MOD;
	}
	}
	return dp[L][N];
	}
	};

view raw Number of Music Playlists.cpp hosted with ❤ by GitHub

我们可以用滚动数组把空间优化到O(N)，代码如下：

	class Solution {
	public:
	int numMusicPlaylists(int N, int L, int K) {
	const int MOD = 1000000007;
	//dp[i][j] represents # of ways we can create playlist with
	//length i and j unique songs, the result is dp[L][N]
	//dp[i][j] = dp[i - 1][j - 1] * (N - j + 1) + dp[i - 1][j] * (j - K)
	//dp[i - 1][j - 1] * (N - j + 1) is # of ways we pick a unique song at i
	//dp[i - 1][j] * (j - K) is # of way we pick a repeated song at i
	vector<vector<long>> dp(2, vector<long>(N + 1, 0));
	dp[0][1] = N;
	int e = 1;
	for (int i = 2; i <= L; ++i, e ^= 1)
	{
	for (int j = 1; j <= min(i, N); ++j)
	{
	dp[e][j] = (dp[e ^ 1][j - 1] * (N - j + 1)) % MOD;
	if (j >= K)dp[e][j] += dp[e ^ 1][j] * (j - K);
	dp[e][j] %= MOD;
	}
	}
	return dp[e ^ 1][N];
	}
	};

view raw Number of Music Playlists_rolling_array.cpp hosted with ❤ by GitHub