Ý tưởng chính đằng sau các mã như sau: " Trên mỗi bước có ways
các cách để thực hiện thay đổi i
số tiền đã cho tiền xu [1,...coin]
".
Vì vậy, trong lần lặp đầu tiên, bạn chỉ có một đồng xu có mệnh giá là 1
. Tôi tin rằng nó là hiển nhiên để thấy rằng chỉ có một cách để cung cấp cho một sự thay đổi chỉ có những đồng tiền cho bất kỳ mục tiêu. Ở bước này, ways
mảng sẽ trông giống như [1,...1]
(chỉ một cách cho tất cả các mục tiêu từ 0
đến target
).
Trong bước tiếp theo, chúng tôi thêm một đồng xu có mệnh giá là 2
vào tập hợp tiền xu trước đó. Bây giờ chúng tôi có thể tính toán số lượng kết hợp thay đổi có cho mỗi mục tiêu từ 0
đến target
. Rõ ràng, số lượng kết hợp sẽ chỉ tăng cho các mục tiêu> = 2
(hoặc đồng tiền mới được thêm vào, trong trường hợp chung). Vì vậy, đối với mục tiêu bằng 2
số kết hợp sẽ là ways[2](old)
+ ways[0](new)
. Thông thường, mỗi khi i
bằng một đồng xu mới được giới thiệu, chúng tôi cần thêm 1
vào số kết hợp trước đó, trong đó một kết hợp mới sẽ chỉ bao gồm một đồng xu.
Đối target
>2
, câu trả lời sẽ bao gồm tổng của "tất cả các kết hợp của target
lượng có tất cả tiền xu ít hơn coin
" và "tất cả các kết hợp của coin
lượng có tất cả tiền xu ít hơn coin
chính nó".
Ở đây tôi mô tả hai bước cơ bản, nhưng tôi hy vọng sẽ dễ dàng khái quát hóa nó.
Hãy để tôi cho bạn thấy một cây tính toán cho target = 4
và coins=[1,2]
:
cách [4] đồng tiền trao = [1,2] =
cách [4] đồng tiền trao = [1] + cách [2] đồng tiền trao = [1,2] =
1 + cách [2] đồng tiền trao = [1] + cách [0] đồng tiền trao = [1,2] =
1 + 1 + 1 = 3
Vì vậy, có ba cách để thay đổi: [1,1,1,1], [1,1,2], [2,2]
.
Mã được đưa ra ở trên hoàn toàn tương đương với giải pháp đệ quy. Nếu bạn hiểu the recursive solution, tôi đặt cược bạn hiểu giải pháp được đưa ra ở trên.