920. Number of Music Playlists

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

难度: Hard

题意：

排一张长度为L首的有顺序的歌单，有N首歌可以选择
每N首歌必须出现一次
两个相同的歌必须隔K首歌才能再次出现
问有多少种排列方式

思路：

排列组合的题目，最重要的是找准排列方向，避免计算重复
先解决第一个条件，每首歌必须出现一次，那么我们先把N首歌放进歌单中，不管顺序先
我们假定已经把N首歌放进歌单，那么其他的位置就随意放，只要满足相同的歌必须隔K个位置
为了避免计算重复，我们规定，这N首歌不管是放在什么位置，都是这首歌在歌单的第一次出现
剩下的就是动态规划了。定义dp[l][n]为歌单的前l个位置中，填入了n首唯一的歌
状态转移有两种情况，
这个位置已经有歌放进来了(因为我们事先填入了N首歌)，排序方式为dp[l-1][n-1]
这个位置没有歌放进来。由于我们的设定，这个位置只能有n首歌选择（因为其他歌还没有第一次出现在歌单）。注意有隔K首歌的问题，前面有K首歌不能选，这K首歌还不一样，为什么呢，因为这K首歌里面，两两之间肯定相隔小于K。所以只有n-k首歌选择，排序方式为dp[l-1][n-1]*(n-K)
由于我们事先把N首歌放进去，这N首歌肯定会有顺序排列。于是最后的结果就等于dp[L][N]*n!

代码：

class Solution {
    private static int MOD = 1000000007;

    public int numMusicPlaylists(int N, int L, int K) {
        int[][] dp = new int[L + 1][N + 1];
        dp[0][0] = 1;
        for (int i = 1;i <= N;i++) {
            dp[0][i] = 0;
        }
        for (int i = 1;i <= L;i++) {
            dp[i][0] = 0;
            for (int j = 1;j <= N;j++) {
                int p = j - Math.min(i - 1, K);
                if (p < 0) {
                    p = 0;
                }
                dp[i][j] = (int) ((long)dp[i - 1][j] * p % MOD);
                dp[i][j] += dp[i - 1][j - 1];
                if (dp[i][j] >= MOD) {
                    dp[i][j] -= MOD;
                }
            }
        }
        int ret = dp[L][N];
        for (int i = 1;i <= N;i++) {
            ret = (int) ((long) ret * i % MOD);
        }
        return ret;
    }
}

我们一直在努力

apachecn/AiLearning