LeetCode 920: Number of Music Playlists

发表于 | | 阅读次数:
字数统计: 537 | 阅读时长 ≈ 2

题目链接

https://leetcode.com/problems/number-of-music-playlists/

题意

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

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

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

其中: 0 <= K < N <= L <= 100

题目类型

动态规划

题目分析

动态规划题目，使用f(n,l)表示剩余听n种歌，l个位置，最小间隔为k时的听歌方案。

转移方程分为两种:

  1. 该位置放的歌前面都没有出现过，则n种歌随便选一种，该种歌前面都不能再选，转移自f(n-1,l-1)
  2. 该位置放的歌前面已经出现过，则最近的k个位置的歌不能再选，只能选(n-k)种，该种歌前面还可以选，转移自f(n,l-1)

有f(n,l) = f(n-1,l-1)*n + f(n,l-1)*(n-k)

边界条件:

  1. n > l 时 l 个位置放不完 n 种歌，为0
  2. n < k + 1 时 不能保证 k 个位置内不出现同种类的歌曲，为0
  3. n == l 时 答案为 n 的全排列，不再多言； n == k + 1 时 答案也是 n 的排列，相当于第一首歌和最后一首歌一定一样其他歌全排列

时间复杂度

$O(N \ast L \ast K)$

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef long long LL;
int f[102][102][102];
int A[102];
class Solution {
public:
    const int Mod = 1000000007;
    Solution() {
        memset(f, -1, sizeof(f));
        A[0] = 1;
        for(int i = 1; i <= 100; i++)
            A[i] = (LL)A[i - 1] * i % Mod;
    }
    int numMusicPlaylists(int N, int L, int K) {
        if (N == L || N == K + 1)
            return A[N];
        if (N > L || N < K + 1)
            return 0;
        if (f[N][L][K] != -1)
            return f[N][L][K];
        int ans = (LL)numMusicPlaylists(N - 1, L - 1, K) * N % Mod;
        ans += (LL)numMusicPlaylists(N, L - 1, K) * (N - K) % Mod;
        ans %= Mod;
        return f[N][L][K] = ans;
    }
};
0%