# 1. Tóm tắt đề bài

Cho một dãy $coins$ gồm toàn các số nguyên, thể hiện các mệnh giá của các đồng tiền có ở nước bạn.

Có bao nhiêu cách để quy đổi giá trị $amount$ thành tổng các đồng tiền khác nhau?

2 cách đồi tiền khác nhau khi tồn tại một mệnh giá $x$ nào đó, mà số lần sử dụng đồng tiền mệnh giá $x$ ở cả hai cách là khác nhau.

##### Giới hạn

$1 \le coins.length \le 300$

$1 \le coins[i] \le 5000$

$0 \le amount \le 5000$

Tất cả các giá trị trong $coins$ đều phân biệt.

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(n * amount)$**

Ta có thể nghĩ đơn giản đến một mảng $dp(i)$ để tính số cách tạo ra $i$ đồng từ các đồng tiền mệnh giá đã cho:

$dp(i) = \sum_{j = 0}^{n - 1} dp(i - coins[j])$

Tuy nhiên, cách này sẽ tính:

$4 = 1 + 2 + 1$ và $4 = 1 + 1 + 2$ là hai cách khác nhau.

Cho nên, ta sẽ phải xem xét bổ sung một chiều nữa cho hàm $dp$ để tính cả thử tự của hàm này.

# 3. Lời giải chi tiết

Gọi $dp(i, j)$ là số cách để tạo ra đồng tiền mệnh giá $j$, khi ta chỉ sử dụng các đồng tiền với mệnh giá $coins[0]$ đến $coins[i]$.

Khi đó, ta có $dp(i, j) = \sum_{k = 0}^{j / coins[i]} dp(i - 1, j - k * coins[i])$.

Hoặc, để đảm bảo độ phức tạp, ta có thể viết lại thành:

$dp(i, j) = dp(i - 1, j) + dp(i, j - coins[i])$.

### Độ phức tạp thuật toán

Thời gian: $O(n * k)$ (do công thức tính cho mỗi ô nhớ là $O(1)$).

Bộ nhớ mở rộng: $O(n * k)$.

# 4. Kết luận & Gợi ý mở rộng

Đây là một bài cơ bản, và đã nằm trong chuyên đề DP của CLB. Các bạn có thể tham khảo thêm các bài toán sau:

[322. Coin Change](https://leetcode.com/problems/coin-change/)
[2218. Maximum Value of K Coins From Piles](https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/)