🎉 Hết phần Level 3!

Bạn vừa hoàn thành cuốn sách 288 câu hỏi coding DSA interview từ Easy đến Hard, cover 44 pattern. Chúc bạn pass mọi vòng phỏng vấn Big Tech!

“The best way to learn is to teach.” - Hãy thử giảng lại 1 chương cho bạn bè. Nếu bạn explain được dễ hiểu, bạn đã thuộc bài.

Bài tự luyện liên quan

• LC 920 - Music Playlists (bài này)
• LC 552 - Student Attendance Record II

Tóm tắt chương & Quyết định

Counting DP framework

• State: gì đặc trưng cho subproblem? (chỉ số, số phần tử đã chọn, parity, last-value…).
• Transition graph: từ state này dẫn đến state nào với count nào?
• Modulo: áp % MOD sau mỗi phép cộng/nhân lớn - tránh int quá to (Python ok, nhưng vẫn quy ước).

Unique Paths (LC 62) - 2 cách

Cách	Time	Space	Khi nào
DP grid dp[i][j] = dp[i-1][j] + dp[i][j-1]	O(mn)	O(mn) hoặc O(min(m,n))	Khi có obstacle (LC 63) hoặc đề mở rộng
Công thức C(m+n-2, m-1)	O(min(m,n))	O(1)	Khi không obstacle

Number of Music Playlists (LC 920) - state

• dp[i][j] = playlist độ dài i dùng đúng j bài khác nhau.
• Transition:
  • Thêm bài mới: dp[i-1][j-1] × (N - (j-1)).
  • Thêm bài cũ (cách bài hiện ≥ K): dp[i-1][j] × max(0, j - K).

Find All Good Strings (LC 1397) - digit DP + KMP

• Đếm chuỗi ≤ s2, ≥ s1, không chứa evil → f(s2) - f(s1 - 1) với f là “đếm ≤ s không chứa evil”.
• State: (idx, kmp_state, is_tight).
• kmp_state = LPS pointer trong evil để detect khi nào sắp khớp.

Count Vowels Permutation (LC 1220) - transition graph

a → e
e → a, i
i → a, e, o, u
o → i, u
u → a

DP dp[i][v] = số chuỗi độ dài i kết thúc bằng nguyên âm v.

---