Chương 44 - Combinatorics kết hợp Dynamic Programming

Chương cuối - DP đếm tổ hợp. Pattern: state là cấu trúc đếm + transition qua phép cộng. Mod 10^9 + 7 xuất hiện ở mọi bài (vì kết quả lớn).

Mục tiêu chương

Sau chương này, bạn sẽ:

• Pattern: state là cấu trúc đếm, transition là tổng (không max/min).
• Mod arithmetic: % MOD ở mọi transition để tránh overflow.
• Bài cốt lõi: Unique Paths (formula vs DP), Knight Dialer, Music Playlists.
• Bitmask kết hợp combinatorics: Number of Ways Hats (assignment counting).

Khi nào dùng pattern này?

• Bài đếm số cách / số path / số sequence.
• DP transition là tổng (không phải max/min).
• Cần modulo 10^9 + 7 thường xuyên.

Template code

MOD = 10**9 + 7

def dp_count(states):
    table = [0] * len(states)
    table[0] = base
    for i in range(1, len(states)):
        table[i] = (sum(table[j] for j in transitions(i)) % MOD)
    return table[-1]

Bài tự luyện cuối chương

• LC 357 - Count Numbers with Unique Digits
• LC 1641 - Count Sorted Vowel Strings
• LC 1411 - Number of Ways to Paint N × 3 Grid

---

44.1 Unique Paths (LC 62)

Đề bài

Lưới m × n. Robot ở (0,0) đi tới (m-1,n-1), chỉ đi phải hoặc xuống. Đếm số path.

Ví dụ

Input:  m=3, n=7
Output: 28

Ràng buộc

• 1 <= m, n <= 100

Clarifying questions

• m hoặc n = 1? → Trả 1.

Hướng tiếp cận

DP dp[i][j] = dp[i-1][j] + dp[i][j-1]. Hoặc combinatorics: C(m+n-2, m-1).

Code Python 3

from math import comb

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, m - 1)

Phân tích độ phức tạp

• Thời gian: O(m + n) với công thức tổ hợp; O(m · n) với DP.
• Bộ nhớ: O(1) formula; O(m · n) DP.

Bình luận

• Trực tiếp combinatorics: chọn m-1 bước xuống trong m+n-2 bước.

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

• LC 63 - Unique Paths II (bài 44.2)
• LC 64 - Minimum Path Sum

---

44.2 Unique Paths II (LC 63)

Đề bài

Như 44.1, có vật cản. 1 = block.

Ví dụ

Input:  obstacleGrid = [[0, 0, 0],
                        [0, 1, 0],
                        [0, 0, 0]]   (0 = ô trống, 1 = vật cản)
Output: 2   (số đường đi từ (0,0) tới (m-1, n-1), chỉ đi xuống/sang phải)

Ràng buộc

• 1 <= m, n <= 100
• obstacleGrid[i][j] ∈ {0, 1}

Clarifying questions

• Obstacle ở (0,0)? → Trả 0.
• Obstacle ở (m-1,n-1)? → Trả 0.

Hướng tiếp cận

DP. Nếu ô block → dp[i][j] = 0.

Code Python 3

from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        if obstacleGrid[0][0] == 1: return 0
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                    continue
                if i > 0: dp[i][j] += dp[i - 1][j]
                if j > 0: dp[i][j] += dp[i][j - 1]
        return dp[-1][-1]

Phân tích độ phức tạp

• Thời gian: O(m · n).
• Bộ nhớ: O(m · n); có thể O(n) rolling.

Bình luận

• Bẫy: ô vật cản tại (0,0) hoặc (m-1, n-1) → trả 0.
• Follow-up: LC 980 (Unique Paths III) - Hamiltonian path.

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

• LC 62 - Unique Paths (bài 44.1)
• LC 980 - Unique Paths III

---

44.3 Knight Dialer (LC 935)

Đề bài

Trên bàn phím số (3×4), knight chess đi n - 1 bước, mỗi bước đi 1 nước knight. Đếm số chuỗi tạo được. Mod 10^9 + 7.

Ví dụ

Input:  n=2
Output: 20

Ràng buộc

• 1 <= n <= 5000

Clarifying questions

• n = 1? → Trả 10 (mỗi phím là 1 chuỗi length 1).

Hướng tiếp cận

Neighbor map cho bàn phím. DP dp[i][digit] = số chuỗi length i kết thúc tại digit.

Code Python 3

class Solution:
    MOD = 10**9 + 7
    NEIGHBORS = {
        0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8], 4: [0, 3, 9],
        5: [], 6: [0, 1, 7], 7: [2, 6], 8: [1, 3], 9: [2, 4]
    }

    def knightDialer(self, n: int) -> int:
        dp = [1] * 10
        for _ in range(n - 1):
            new_dp = [0] * 10
            for d in range(10):
                for nb in self.NEIGHBORS[d]:
                    new_dp[nb] = (new_dp[nb] + dp[d]) % self.MOD
            dp = new_dp
        return sum(dp) % self.MOD

Phân tích độ phức tạp

• Thời gian: O(n).
• Bộ nhớ: O(1) (chỉ 10 phím).

Bình luận

• Matrix exponentiation giải O(log n) - cho n cực lớn.

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

• LC 70 - Climbing Stairs
• LC 1220 - Count Vowels Permutation (bài 44.4)

---

44.4 Count Vowels Permutation (LC 1220)

Đề bài

Đếm số chuỗi nguyên âm độ dài n với rules: - ‘a’ chỉ sau ‘e’. - ‘e’ chỉ sau ‘a’ hoặc ‘i’. - ‘i’ không sau ‘a’ hoặc ‘i’. - ‘o’ chỉ sau ‘i’ hoặc ‘u’. - ‘u’ chỉ sau ‘i’.

Ví dụ

Input:  n=1
Output: 5

Ràng buộc

• 1 <= n <= 2·10^4

Clarifying questions

• n = 1? → Trả 5 (mỗi vowel là 1 chuỗi length 1).

Hướng tiếp cận

DP dp[i][v] = số chuỗi length i kết thúc tại nguyên âm v.

Code Python 3

class Solution:
    MOD = 10**9 + 7

    def countVowelPermutation(self, n: int) -> int:
        # Index: 0=a, 1=e, 2=i, 3=o, 4=u
        # Transitions backwards: ai có thể đứng trước cái này.
        prev_can = {
            0: [1, 2, 4],     # a sau e, i, u
            1: [0, 2],         # e sau a, i
            2: [1, 3],         # i sau e, o
            3: [2],            # o sau i
            4: [2, 3],         # u sau i, o
        }
        dp = [1] * 5
        for _ in range(n - 1):
            new_dp = [0] * 5
            for v in range(5):
                for prev in prev_can[v]:
                    new_dp[v] = (new_dp[v] + dp[prev]) % self.MOD
            dp = new_dp
        return sum(dp) % self.MOD

Phân tích độ phức tạp

• Thời gian: O(n).
• Bộ nhớ: O(1) (5 vowel).

Bình luận

• Bẫy: transition phải đúng theo rule (a sau e/i/u, etc.).
• Follow-up: LC 935 (Knight Dialer) cùng pattern transition.

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

• LC 935 - Knight Dialer (bài 44.3)
• LC 1411 - Number of Ways to Paint N × 3 Grid

---

44.5 Number of Ways to Wear Different Hats to Each Other (LC 1434)

Đề bài

40 nón, n người (n ≤ 10), mỗi người có list nón mình thích. Đếm số cách phân nón sao cho mỗi người 1 nón khác nhau.

Ví dụ

Input:  hats = [[3, 4], [4, 5], [5]]
        (hats[i] = danh sách mũ mà người i thích; nhãn mũ ∈ [1, 40])
Output: 1   (số cách gán cho mỗi người đúng 1 mũ, các mũ phải khác nhau; mod 10^9 + 7)

Ràng buộc

• n == len(hats)
• 1 <= n <= 10

Clarifying questions

• n = 0? → Trả 1.
• Một người không có nón nào? → Trả 0.

Hướng tiếp cận

Bitmask DP trên người, iterate qua nón (vì người ≤ 10, nón ≤ 40):

dp[hat][mask] = số cách dùng nón <= hat để cover các người trong mask.

Code Python 3

from collections import defaultdict
from typing import List

class Solution:
    MOD = 10**9 + 7

    def numberWays(self, hats: List[List[int]]) -> int:
        n = len(hats)
        hat_to_people = defaultdict(list)
        for p, hs in enumerate(hats):
            for h in hs:
                hat_to_people[h].append(p)

        full = (1 << n) - 1
        dp = [0] * (1 << n)
        dp[0] = 1
        for h in range(1, 41):
            new_dp = dp[:]
            for mask in range(1 << n):
                for p in hat_to_people[h]:
                    if mask & (1 << p): continue
                    new_dp[mask | (1 << p)] = (new_dp[mask | (1 << p)] + dp[mask]) % self.MOD
            dp = new_dp
        return dp[full]

Phân tích độ phức tạp

• Thời gian: O(40 · 2^n · n) với n ≤ 10.
• Bộ nhớ: O(2^n).

Bình luận

• Bẫy: iterate qua hat (40) × mask (2^n) thay vì người × hat - tránh blow-up state.
• Follow-up: LC 1125 (Smallest Sufficient Team) - Chương 40.3.

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

• LC 1125 - Smallest Sufficient Team (Chương 40.3)
• LC 526 - Beautiful Arrangement

---

44.6 Number of Music Playlists (LC 920)

Đề bài

Có n bài hát, listen goal bài. Mỗi bài nghe ít nhất 1 lần. Khoảng cách giữa 2 lần nghe cùng bài ≥ k. Đếm số playlist.

Ví dụ

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

Ràng buộc

• 0 <= k < n <= goal <= 100

Clarifying questions

• n > goal? → Không đủ chỗ cho n bài → trả 0.
• k = 0? → Như permutation thông thường.

Hướng tiếp cận

DP dp[i][j] = số playlist length i dùng j bài phân biệt.

• Thêm bài mới: dp[i][j] += dp[i-1][j-1] * (n - (j-1)).
• Thêm bài cũ (đảm bảo > k bài trước): dp[i][j] += dp[i-1][j] * max(0, j - k).

Code Python 3

class Solution:
    MOD = 10**9 + 7

    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        dp = [[0] * (n + 1) for _ in range(goal + 1)]
        dp[0][0] = 1
        for i in range(1, goal + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i - 1][j - 1] * (n - j + 1) % self.MOD
                if j > k:
                    dp[i][j] = (dp[i][j] + dp[i - 1][j] * (j - k)) % self.MOD
        return dp[goal][n]

Phân tích độ phức tạp

• Thời gian: O(n · goal).
• Bộ nhớ: O(n · goal); có thể O(n) rolling.

Bình luận

• Bài Hard. Cốt lõi: tách trường hợp “bài mới” vs “bài cũ” + đảm bảo constraint khoảng cách.

---