[Quy hoạch động] [SPOJ] DTDOI

Đề bài
Dễ có công thức truy hồi
f[i] = min(f[i],f[i-a[j]]+1) với i là số tiền cần đổi, khởi tạo f[i]=oo (dương vô cùng).
Tuy vậy, do s quá lớn nên ta tham bằng cách đổi gần hết s bằng mệnh giá lớn nhất, sau đó quy hoạch động phần tiền thừa còn lại.
Code