จำนวนเพลย์ลิสต์เพลงใน C++

คำอธิบายปัญหา

มีเพลง N เพลง ต้องการฟัง L เพลง เงื่อนไข:

• ทุกเพลงเล่นอย่างน้อย 1 ครั้ง
• เพลงเดิมจะเล่นซ้ำได้ก็ต่อเมื่อมีเพลงอื่น K เพลงถูกเล่นระหว่างนั้น

หาจำนวนเพลย์ลิสต์ที่เป็นไปได้ modulo 10⁹+7

ตัวอย่าง

N=2, L=3, K=0 → Output: 6
[1,1,2], [1,2,1], [2,1,1], [2,2,1], [2,1,2], [1,2,2]

แนวทางแก้ปัญหา: Dynamic Programming

State: dp[i][j] = จำนวนเพลย์ลิสต์ยาว i ที่ใช้เพลงต่างกัน j เพลง

Transition:

• เพิ่มเพลงใหม่: dp[i][j] += dp[i-1][j-1] × (N - (j-1))
• เพิ่มเพลงเก่า (ต้องมี j > K): dp[i][j] += dp[i-1][j] × (j - K)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
typedef long long lli;

class Solution {
    int add(lli a, lli b) { return (a%MOD + b%MOD)%MOD; }
    int mul(lli a, lli b) { return (a%MOD * b%MOD)%MOD; }
    
public:
    int numMusicPlaylists(int N, int L, int K) {
        vector<vector<int>> dp(L+1, vector<int>(N+1, 0));
        dp[0][0] = 1;
        
        for(int i=1; i<=L; i++) {
            for(int j=1; j<=N; j++) {
                // เพิ่มเพลงใหม่
                dp[i][j] = mul(dp[i-1][j-1], N - (j-1));
                // เพิ่มเพลงเก่า (ต้องมี j > K)
                if(j > K) {
                    dp[i][j] = add(dp[i][j], mul(dp[i-1][j], j - K));
                }
            }
        }
        return dp[L][N];
    }
};

ความซับซ้อน

• เวลา: O(L × N)
• พื้นที่: O(L × N) (สามารถลดเหลือ O(N) ได้)