Hướng dẫn thuật toán - Đăng - Chuyên Sơn La Online Judge

Mục tiêu: Tìm số cách kết hợp các đồng xu để có tổng bằng .
Đặc điểm quan trọng: Thứ tự các đồng xu có quan trọng (ví dụ: khác với ). Đây thực chất là bài toán tìm số hoán đổi các đồng xu để đạt tổng .
Ràng buộc: lên đến và đến , vì vậy thuật toán cần có độ phức tạp khoảng .

Sử dụng Quy hoạch động (Dynamic Programming):

Gọi dp[i] là số cách khác nhau để tạo ra tổng số tiền bằng i.
Để có được tổng bằng i, bước cuối cùng ta có thể đã chọn một đồng xu mệnh giá bất kỳ từ tập hợp đồng xu (với điều kiện ).
Khi đó, số cách để tạo ra tổng i chính là tổng của tất cả các cách tạo ra số tiền với mọi đồng xu .

Khởi tạo:
- Tạo một mảng dp kích thước và gán tất cả giá trị ban đầu bằng .
- Đặt dp[0] = 1 (có duy nhất 1 cách để tạo ra tổng bằng 0 là không chọn đồng xu nào).
Trạng thái chuyển đổi (Công thức truy hồi):
- Duyệt từ đến (tính toán số cách cho từng tổng tiền tăng dần):
  - Với mỗi , duyệt qua từng mệnh giá đồng xu trong danh sách.
  - Nếu , ta cập nhật: dp[i] = (dp[i] + dp[i - c_j]) % (10^9 + 7).
Kết quả:
- Giá trị nằm tại dp[x] chính là đáp án cần tìm.

Thứ tự vòng lặp: Để tính số hoán vị (thứ tự quan trọng), vòng lặp duyệt tổng tiền i phải nằm bên ngoài và vòng lặp duyệt các đồng xu c_j nằm bên trong. (Nếu đảo ngược hai vòng lặp này, bạn sẽ tính số tổ hợp - nơi thứ tự không quan trọng).
Xử lý Modulo: Vì kết quả có thể rất lớn, hãy thực hiện phép chia lấy dư % (10^9 + 7) ngay tại mỗi bước cộng trong vòng lặp để tránh tràn số.
Kiểu dữ liệu:
- Trong C++: Nên dùng mảng int hoặc long long và cẩn thận với giới hạn thời gian (10^8 phép tính có thể mất gần 1 giây).
- Trong Python: Do Python xử lý số nguyên lớn tốt nhưng tốc độ vòng lặp chậm, cần tối ưu bằng cách sử dụng PyPy hoặc các kỹ thuật giảm thiểu truy cập mảng.