解題說明
Number of Music Playlists
題目描述：
有 n 首不同的歌曲，要建立一個長度為 goal 的播放清單，滿足：(1) 每首歌至少播放一次；(2) 同一首歌再次播放前，必須間隔至少 k 首其他歌曲。求有多少種不同的播放清單（結果取模 10^9 + 7）。
解題思路：
動態規劃：定義 dp[i][j] = 長度為 i 的播放清單中恰好包含 j 首不同歌曲的方案數。
轉移：考慮第 i 首歌的選擇：
- 新歌：從未播放的歌中選一首，有
(n - j + 1)種選擇 →dp[i-1][j-1] * (n - j + 1)。 - 舊歌：從已播放的
j首中選一首重播，但受限於間隔k，可選的歌有max(j - k, 0)首 →dp[i-1][j] * max(j - k, 0)。
基礎情況：dp[0][0] = 1。
答案：dp[goal][n]。
C++ 解法
複雜度分析
時間複雜度：O(goal * n) — 雙重迴圈遍歷所有 (長度, 歌曲數) 狀態。
空間複雜度：O(goal * n) — 二維 DP 陣列。可優化為 O(n)（滾動陣列）。
虛擬碼
1. Initialize dp[goal+1][n+1] with zeros; set dp[0][0] = 1.
2. For i from 1 to goal:
For j from 1 to min(i, n):
a. dp[i][j] += dp[i-1][j-1] * (n - j + 1) // new song
b. dp[i][j] += dp[i-1][j] * max(j - k, 0) // replay old song
c. Take modulo.
3. Return dp[goal][n].其他解法
容斥原理（Inclusion-Exclusion）：先計算「至少用 j 首歌」的方案數，再用容斥得到「恰好用 n 首歌」的答案。時間 O(n^2)，但推導較複雜。
滾動陣列優化空間：注意到 dp[i] 只依賴 dp[i-1]，可用一維陣列 + 反向遍歷將空間壓縮到 O(n)。時間不變。
延伸思考
- 為什麼重播舊歌時可選的歌曲數是
max(j - k, 0)而非j - k？ - 如何用滾動陣列將空間複雜度從 O(goal * n) 降至 O(n)？
- 若取消「每首歌至少播一次」的限制，DP 的定義和轉移會如何變化？