leetcode 920

问题

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:

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

Example 2:

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

Example 3:

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

Note:

  1. 0 <= K < N <= L <= 100

分析

这道题看了讨论区最高 vote 的答案也是在 K 约束的状态转移有些懵逼，最后看博客才知道是对题目描述产生了问题。K 约束的含义是，当一首歌要重复播放时，这两次播放之间一定至少有 K 首其他的歌被播放。

dp[i][j] 表示一共播放了 i 首歌，其中不同的歌有 j 种的播放列表的数量。

下面来考虑状态转移方程，在加入一首歌的时候，此时有两种情况：

  • 当加入的是一首新歌，则表示之前的 i-1 首歌中有 j-1 首不同的歌曲，其所有的组合情况都可以加上这首新歌，那么当前其实有 N-(j-1) 首新歌可以选。
  • 当加入的是一首重复的歌，则表示之前的 i-1 首歌中已经有了 j 首不同的歌，那么若没有K的限制，则当前有 j 首重复的歌可以选。但是现在有了K的限制，意思是两首重复歌中间必须要有K首其他的歌，则当前只有 j-K 首可以选。而当 j<K 时，其实这种情况是为0的。

综上所述可以得到状态转移方程：

1
2
3
4
5
            dp[i-1][j-1]*(N-(j-1)) + dp[i-1][j]*(j-k)    (j > K)
           /
dp[i][j] = 
           \
            dp[i-1][j-1]*(N-(j-1))   (j <= K)

https://www.cnblogs.com/grandyang/p/11741490.html

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    const int mod = 1000000007;
    int numMusicPlaylists(int N, int L, int K) {
        vector<vector<long long>> dp(L+1, vector<long long>(N+1, 0));
        dp[0][0] = 1;
        for (int i = 1; i <= L; ++i) {
            for (int j = 1; j <= N; ++j) {
                dp[i][j] = (dp[i-1][j-1] * (N-j+1)) % mod;
                if (j > K) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j]*(j-K)) % mod;
                }
            }
        }
        return dp[L][N];
    }
};