format vỡ lung tung, nên click vào link
viết giải thích dài dòng lắm
gọi số cách thối tiền là w(n, V) với:
- n là số tiền cần thối, ví dụ 15,
- V là mảng chứa mệnh giá tiền, ví dụ [10,5,2]
thì với đệ quy phải tìm cách đi tới w(n, V) với bước đi nhỏ nhất. Ở đây số cách thối 15 đồng có thể hiểu là bằng số cách thối 13 đồng (thêm 2 đồng nữa là thành 15). Nhưng chưa hết, vì với cách tính này thì 15 đồng tiền thối lúc nào cũng có tờ 2 đồng, vì vậy còn phải đếm các lần thối ko cần tờ 2 đồng nữa, hay w(15, [10,5,2]) = w(13, [10,5,2]) + w(15, [10,5]). Ở đây chỉ cần xét 1 loại mệnh giá thôi vì các mệnh giá kia sẽ được xử lý trong w(15, [10,5]) hay w(13, [10,5,2]).
để viết công thức tổng quát thì cần thêm 1 biến m nữa, là số lượng tờ tiền trong V. w(n, V) chuyển thành W(n, V, m). Viết W(15, [10,5,2], 3) hiểu là w(15, [10,5,2]); W(15, [10,5,2], 2) hiểu là w(15, [10,5]). Quy ước thêm nữa V[1] là mệnh giá đầu tiên trong V, V[m] là mệnh giá cuối cùng.
vậy ta có công thức đệ quy tổng quát: W(n, V, m) = W(n - V[m], V, m) + W(n, V, m-1)
đệ quy thì phải có điều kiện dừng, hay base cases. Điều kiện dừng ở đây là
- nếu n = 0, thì W(0, V, m) = 1
- nếu n < 0, thì W(n, V, m) = 0
- nếu n > 0 và m < 1, thì W(n, V, m) = 0
code C++14:
#include <iostream>
#include <vector>
using IntArray = std::vector<int>;
int W(int n, const IntArray& V, int m)
{
if (n == 0) return 1;
if (n < 0 || m < 1) return 0;
return W(n - V[m-1], V, m) + W(n, V, m-1);
}
int main()
{
IntArray V{50,20,10,5,2};
std::cout << W(325, V, V.size()) << "\n";
std::cout << W(876, V, V.size()) << "\n";
std::cout << W(3, V, V.size()) << "\n";
}
cách này hơi chậm vì là đệ quy. Muốn nhanh hơn thì xài quy hoạch động, nói đơn giản là lưu lại các giá trị đã tính rồi để ko phải tính lại như đệ quy nữa.
với quy hoạch động thì đi ngược lại từ nhỏ lên. Ở đây n tối đa là 1000 (10 triệu, mà là bội của 10 ngàn, nên chỉ có 1000 giá trị từ 1 tướng ứng với 10 ngàn tới 1000 tương ứng với 10 triệu), nên làm hẳn cái mảng 1000+1 phần tử luôn (thêm số 0), rồi đi từ nhỏ tới lớn. Kiểu na ná như Fibonacci ấy. Fibonacci đệ quy là F(n) = F(n-1) + F(n-2), thì thay vì đi từ F(1000) xuống F(999), F(998), F(997), v.v… thì ta có thể đi từ F(0) F(1) F(2) lên F(1000).
ở đây khó hơn vì W(n, V, m) có tới 2 giá trị thay đổi là n và m. Cách giải là giữ nguyên 1 giá trị, ở đây là m, rồi tính W với n từ 0 tới 1000. Sau đó tăng m lên 1 đơn vị, rồi tính lại W từ 0 tới 1000, v.v… tới khi m = size(V).
với m ko đổi, ta có W(n, V, m) = [COLOR="#008000"]W(n, V, m) +[/COLOR] W(n - V[m], V, m). Sở dĩ phải cộng dồn là vì m thay đổi, nên phần xanh lá thực chất chính là từ m cũ, hay là W(n, V, m-1).
ví dụ n = 15, V = [10,5,2]. Ta tạo mảng p[0…15] gồm 16 phần tử, p[0] = 1 vì có đúng 1 cách thối 0 đồng:
[FONT=Courier New] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
m=0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0[/FONT]
với m = 1, bắt đầu từ p[10] tới p[15], gán p[i] += p[i-10]
[FONT=Courier New] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
m=1 1 0 0 0 0 0 0 0 0 0 [COLOR="#FF0000"]1 0 0 0 0 0[/COLOR][/FONT]
với m = 2, bắt đầu từ p[5] tới p[15], gán p[i] += p[i-5]
[FONT=Courier New] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
m=2 1 0 0 0 0 [COLOR="#FF0000"]1 0 0 0 0 2 0 0 0 0 2[/COLOR][/FONT]
với m = 3, bắt đầu từ p[2] tới p[15], gán p[i] += p[i-2]
[FONT=Courier New] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
m=3 1 0 [COLOR="#FF0000"]1 0 1 1 1 1 1 1 3 1 3 1 3 3[/COLOR][/FONT]
cho test mảng dữ liệu 10^6 mảng mệnh giá 1000 mới fer 
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?