Làm thế nào để giải quyết bài toán Đếm số lượng đường đi hoặc cấu hình thỏa mãn điều kiện phức tạp bằng Dynamic Programming kết hợp với Tổ hợp hoặc Toán học mô đun?

Question

Accepted Answer

Khi phỏng vấn ở cấp độ Middle, các bài toán quy hoạch động không chỉ dừng lại ở việc tìm giá trị lớn nhất hay nhỏ nhất, mà còn mở rộng sang bài toán đếm số lượng cấu hình hợp lệ.
Bản chất cơ chế hoạt động

Công thức chuyển trạng thái thường là tổng các cách từ các trạng thái tiền nhiệm: dp[i] = (dp[i] + dp[i - k]) % MOD.
Do kết quả có thể cực kỳ lớn, việc áp dụng Phép toán Mô đun (Modulo Arithmetic) tại mọi bước cộng dồn là bắt buộc để tránh tràn số.
Đối với các bài toán có ràng buộc không gian lớn, cần kết hợp với lũy thừa ma trận (Matrix Exponentiation) để tối ưu độ phức tạp thời gian từ $O(N)$ xuống $O(\log N)$.

Ví dụ minh họa
# Bài toán đếm số cách leo cầu thang khi có thể bước 1, 2 hoặc 3 bước
def count_ways(n, mod=1000000007):
    if n <= 0:
        return 0
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        if i >= 1:
            dp[i] = (dp[i] + dp[i - 1]) % mod
        if i >= 2:
            dp[i] = (dp[i] + dp[i - 2]) % mod
        if i >= 3:
            dp[i] = (dp[i] + dp[i - 3]) % mod
    return dp[n]
Lưu ý kinh nghiệm thực chiến

Luôn thực hiện phép tính % MOD ngay sau mỗi phép cộng hoặc nhân trong vòng lặp để ngăn chặn tràn số nguyên (Integer Overflow) ở các ngôn ngữ như Java hoặc C++.
Cẩn trọng với các trường hợp biên như n = 0 hoặc các giá trị âm.

Làm thế nào để giải quyết bài toán Đếm số lượng đường đi hoặc cấu hình thỏa mãn điều kiện phức tạp bằng Dynamic Programming kết hợp với Tổ hợp hoặc Toán học mô đun?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi dynamic programming liên quan cùng chủ đề