[Swift]LeetCode920. 播放列表的数量 | Number of Music Playlis

发布时间：2020-12-14 05:11:16 所属栏目：百科来源：网络整理

导读：Your music player contains? N ?different songs and she wants to listen to? L ?(not necessarily different) songs during your trip. ?You?create?a playlist so?that: Every song is played at least once A song can only be played again only if? K

Your music player contains?N?different songs and she wants to listen to?L?(not necessarily different) songs during your trip. ?You?create?a playlist so?that:

Every song is played at least once
A song can only be played again only if?K?other songs have been played

Return the number of possible playlists.??As the answer can be very large,return it modulo?10^9 + 7.

Example 1:

Input: N = 3,L = 3,K = 1 Output: 6 Explanation: There are 6 possible playlists. [1,2,3],[1,3,2],[2,1,1],[3,1].

Example 2:

Input: N = 2,L = 3,K = 0 Output: 6 Explanation: There are 6 possible playlists. [1,2]

Example 3:

Input: N = 2,L = 3,K = 1 Output: 2 Explanation: There are 2 possible playlists. [1,2]

Note:

0 <= K < N <= L <= 100

你的音乐播放器里有?N?首不同的歌，在旅途中，你的旅伴想要听?L?首歌（不一定不同，即，允许歌曲重复）。请你为她按如下规则创建一个播放列表：

每首歌至少播放一次。
一首歌只有在其他?K?首歌播放完之后才能再次播放。

返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回它模?10^9 + 7?的结果。

示例 1：

输入：N = 3,L = 3,K = 1
输出：6
解释：有 6 种可能的播放列表。[1,3]，[1,2]，[2,3]，[2,1]，[3,2]，[3,1].

示例 2：

输入：N = 2,K = 0
输出：6
解释：有 6 种可能的播放列表。[1,2]，[1,1]，[2,2]

示例 3：

输入：N = 2,K = 1
输出：2
解释：有 2 种可能的播放列表。[1,2]

提示：

0 <= K < N <= L <= 100

56 ms

 1 class Solution {
 2     func numMusicPlaylists(_ N: Int,_ L: Int,_ K: Int) -> Int {
 3         var mod:Int = 1000000007
 4         var dp = Array(repeating:0,count: N+1)
 5         dp[0] = 1
 6         for i in 0..<L
 7         {
 8             var ndp = Array(repeating:0,count: N+1)
 9             for j in 0..<N
10             {
11                 ndp[j + 1] += dp[j] * (N-j)
12                 ndp[j + 1] %= mod
13             }
14             for j in 0...N
15             {
16                 ndp[j] += dp[j] * max(j - K,0)
17                 ndp[j] %= mod
18             }
19             dp = ndp
20         }
21         return Int(dp[N])
22     }
23 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!