920. Number of Music Playlists

Hard

Description

你有 n 首不同的歌，要建立一個長度為 goal 的播放清單。規則：每首歌至少播放一次；一首歌再次播放前，必須先播放 k 首其他歌。回傳可能的播放清單數量（對 10^9+7 取餘）。

Example:

Input: n = 3, goal = 3, k = 1 Output: 6

Intuition#

第 i 首歌可以是新歌（有 n - j + 1 種選擇）或舊歌（有 max(0, j - k) 種選擇，因為最近 k 首不能重複）
轉移方程：dp[i][j] = dp[i-1][j-1] * (n-j+1) + dp[i-1][j] * max(j-k, 0)

Approaches#

1: 2D DP#

概念: 建立 dp[goal+1][n+1] 表格，按轉移方程填表。
時間複雜度: O(goal * n)
空間複雜度: O(goal * n)

class Solution {
    fun numMusicPlaylists(n: Int, goal: Int, k: Int): Int {
        val MOD = 1_000_000_007L
        val dp = Array(goal + 1) { LongArray(n + 1) }
        dp[0][0] = 1

        for (i in 1..goal) {
            for (j in 1..minOf(i, n)) {
                dp[i][j] = dp[i - 1][j - 1] * (n - j + 1) % MOD
                dp[i][j] = (dp[i][j] + dp[i - 1][j] * maxOf(j - k, 0) % MOD) % MOD
            }
        }
        return dp[goal][n].toInt()
    }
}

⭐2: 1D DP（空間優化）#

概念: 由於 dp[i][j] 只依賴 dp[i-1][j-1] 和 dp[i-1][j]，可壓縮為一維陣列，逆序更新。
時間複雜度: O(goal * n)
空間複雜度: O(n)

class Solution {
    fun numMusicPlaylists(n: Int, goal: Int, k: Int): Int {
        val MOD = 1_000_000_007L
        val dp = LongArray(n + 1)
        dp[0] = 1

        for (i in 1..goal) {
            for (j in minOf(i, n) downTo 1) {
                dp[j] = (dp[j - 1] * (n - j + 1) % MOD + dp[j] * maxOf(j - k, 0) % MOD) % MOD
            }
            dp[0] = 0
        }
        return dp[n].toInt()
    }
}

🔑 Takeaways#

Pattern: 計數型 DP — 新歌 vs 舊歌的選擇
關鍵技巧: 「新歌」有 n-j+1 種選擇，「舊歌」受 k 間隔限制只有 max(j-k, 0) 種；逆序更新壓縮空間