[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)。代码如下：

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