Bài toán đổi tiền

Bài toán đổi tiền xu là một bài toán kinh điển trong lập trình động. Cho một tập hợp các đồng xu có mệnh giá khác nhau và một tổng số tiền, nhiệm vụ là tìm số đồng xu ít nhất cần dùng để tạo thành số tiền đã cho.

Ví dụ, giả sử ta có các đồng xu với mệnh giá [1, 5, 10] và muốn tạo thành số tiền 15. Số đồng xu ít nhất cần dùng là 2 (một đồng 10 và một đồng 5).

Để giải bài toán này bằng lập trình động, ta có thể tạo một bảng với các hàng biểu thị mệnh giá của các đồng xu và các cột biểu thị số tiền từ 0 đến tổng số tiền đã cho. Sau đó, ta điền vào bảng theo cách từ dưới lên bằng cách tính số đồng xu ít nhất cần dùng để tạo thành mỗi số tiền, sử dụng các đồng xu của từng mệnh giá.