920. Number of Music Playlists

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

920Number of Music Playlists2-D DPHard2-D DP

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

Example:

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

Intuition

TIP

dp[i][j] 表示播放清單長度為 i、包含 j 首不同歌曲的方案數。

第 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 — O(goal * n) / O(goal * n)

Idea: 建立 dp[goal+1][n+1] 表格，按轉移方程填表。
Time: O(goal * n)
Space: 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 (Space Optimized) — O(goal * n) / O(n)

Idea: 由於 dp[i][j] 只依賴 dp[i-1][j-1] 和 dp[i-1][j]，可壓縮為一維陣列，逆序更新。
Time: O(goal * n)
Space: 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 舊歌的選擇
Key trick: 「新歌」有 n-j+1 種選擇，「舊歌」受 k 間隔限制只有 max(j-k, 0) 種；逆序更新壓縮空間

Intuition

Approaches

🔑 Takeaways

相關題目