Coin Change
Bạn có danh sách coins gồm các giá trị xu khác nhau và một amount mục tiêu. Bạn có thể dùng mỗi giá trị xu bao nhiêu lần tùy ý. Hãy trả về số xu ít nhất có tổng giá trị đúng bằng amount, hoặc -1 nếu không có cách kết hợp xu nào đạt được tổng đó. Với amount bằng 0, cần 0 xu.
Hàm
- coinsinteger-array
- các mệnh giá xu khác nhau, mỗi mệnh giá có thể dùng bất kỳ số lần nào
- amountinteger
- tổng số tiền cần thanh toán chính xác
- Trả vềinteger
- số xu ít nhất cần dùng, hoặc -1 nếu không thể tạo ra số tiền đó
Ràng buộc
1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 1040 ≤ amount ≤ 104- Tất cả giá trị xu đều khác nhau.
Ví dụ
- Đầu vào
- coins = [2, 5, 10]amount = 27
- Đầu ra
- 4
- Giải thích
- 10 + 10 + 5 + 2 tạo thành 27 bằng bốn đồng xu. Ba đồng xu không đủ: 27 là số lẻ, nên cần đúng một đồng 5, còn hai đồng kia cộng lại nhiều nhất là 20, chưa đủ 22.
- Đầu vào
- coins = [4, 6]amount = 7
- Đầu ra
- -1
- Giải thích
- Cả hai giá trị xu đều là số chẵn, nên mọi tổng bạn có thể tạo ra đều là số chẵn. 7 là số lẻ, nên đáp án là -1.
- Đầu vào
- coins = [3, 7]amount = 0
- Đầu ra
- 0
- Giải thích
- Trả 0 thì không tốn đồng nào, nên đáp án luôn là 0, bất kể giá trị các đồng xu là bao nhiêu.
Câu hỏi mở rộng
Bạn có thể đếm số cách kết hợp các đồng xu để tổng bằng amount không, thay vì tìm số đồng xu ít nhất?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Luôn chọn đồng xu lớn nhất có thể dùng không phải lúc nào cũng giúp bạn dùng ít đồng xu nhất. Hãy thử với các đồng xu
[1, 3, 4]và số tiền6.Giả sử bạn đã biết số đồng xu ít nhất cho mọi số tiền nhỏ hơn
t. Có thể dùng thêm một đồng xu để đạt đượcttừ những số tiền nhỏ hơn nào?Điền vào bảng
fewest[0..amount]theo thứ tự từ0trở lên:fewest[0] = 0, và mỗifewest[t]bằng giá trị tốt nhất củafewest[t - c]cộng thêm một, xét các đồng xuc <= t. Đánh dấu các số tiền không thể đạt được bằng một giá trị lớn hơn mọi đáp án thực tế, chẳng hạn nhưamount + 1, rồi đổi giá trị đó thành-1ở cuối.
Lời giải
Chọn đồng xu lớn nhất có thể dùng sẽ không hiệu quả: với các đồng xu 1, 3 và 4, cách này trả 6 bằng 4 + 1 + 1, trong khi 3 + 3 chỉ cần hai đồng xu. Số đồng xu ít nhất cho một số tiền chỉ phụ thuộc vào số đồng xu ít nhất cần cho các số tiền nhỏ hơn, vì vậy bạn giải từng số tiền từ 0 đến amount một lần.
Thử mọi tổ hợp bằng đệ quy
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Nếu đồng xu cuối cùng bạn trả có giá trị là c, thì những đồng xu trước đó cần trả số tiền remaining - c với số xu ít nhất có thể. Vì vậy, fewest(remaining) bằng 1 cộng với giá trị nhỏ nhất của fewest(remaining - c) trong số mọi đồng xu phù hợp. Cách này thử mọi chuỗi đồng xu có tổng không vượt quá số tiền cần trả, nên không thể bỏ sót cách tốt nhất.
Cách này giải cùng một số tiền hết lần này đến lần khác. Với các đồng xu mệnh giá 2, 5 và 10, số tiền 27 dẫn đến việc tính số tiền 15 sau khi trả 10 + 2, 2 + 10, 5 + 5 + 2 và nhiều thứ tự khác, rồi tính lại số tiền 15 từ đầu mỗi lần. Số lần gọi tăng theo cấp số nhân cùng với số tiền.
Thuật toán
- Viết một hàm trợ giúp
fewest(remaining)trả về số xu ít nhất cần dùng choremaining, hoặc -1 nếu không có cách nào phù hợp. - Nếu
remainingbằng 0, hãy trả về 0. - Với mỗi đồng xu có giá trị không lớn hơn
remaining, hãy gọi hàm trợ giúp với số tiền còn lại sau khi trả đồng xu đó. - Giữ lại kết quả nhỏ nhất khác -1, rồi cộng thêm 1 cho đồng xu bạn đã dùng.
- Trả về số xu đó, hoặc -1 nếu mọi đồng xu đều không cho ra kết quả. Đáp án là
fewest(amount).
def coinChange(coins, amount):
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
return best
return fewest(amount)Đệ quy với memoization
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Đệ quy chỉ hỏi về các số tiền từ 0 đến amount. Lần đầu tính ra mỗi đáp án, hãy lưu vào một mảng và trả về giá trị đã lưu khi số tiền đó xuất hiện lần nữa. Mỗi số tiền chỉ được giải một lần bằng cách duyệt qua các đồng xu bằng một vòng lặp: độ phức tạp O(amount × coins).
Các lời gọi vẫn lồng nhau một cấp cho mỗi đồng xu được thanh toán. Với đồng xu có giá trị 1, độ sâu có thể lên đến 10^4 cấp, vượt quá giới hạn ngăn xếp lời gọi mặc định trong nhiều ngôn ngữ.
Thuật toán
- Tạo một mảng
memocó chỗ cho mọi số tiền từ 0 đếnamount, chứa một dấu đánh dấu rằng giá trị vẫn chưa được tính. - Trong
fewest(remaining), trả về 0 nếu giá trị là 0, và trả vềmemo[remaining]nếu ô đó đã chứa kết quả. - Nếu không, hãy thử mọi đồng xu phù hợp như trong cách đệ quy đơn giản, rồi giữ lại kết quả nhỏ nhất cộng thêm 1.
- Lưu kết quả, kể cả -1, vào
memo[remaining]trước khi trả về. - Trả về
fewest(amount).
def coinChange(coins, amount):
# memo[r] holds the answer for r once it is worked out; None means not yet
memo = [None] * (amount + 1)
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
if memo[remaining] is not None:
return memo[remaining]
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
memo[remaining] = best
return best
return fewest(amount)Quy hoạch động từ dưới lên theo các mức tiền
Ý tưởng
Điền bảng fewest từ 0 trở lên. Khi bạn đạt đến tổng t, mọi tổng nhỏ hơn đều đã được giải quyết, nên fewest[t] bằng 1 cộng với giá trị fewest[t-c] nhỏ nhất trong các đồng xu c có giá trị không vượt quá tổng đó.
Những tổng không thể tạo thành từ bất kỳ tổ hợp đồng xu nào sẽ giữ giá trị đánh dấu amount + 1. Mỗi đồng xu có giá trị ít nhất là 1, nên một đáp án thực tế không bao giờ dùng quá amount đồng xu, và giá trị đánh dấu luôn thua trong mọi phép so sánh. Vòng lặp thay thế đệ quy, nên độ sâu của ngăn xếp lời gọi không còn quan trọng.
Thuật toán
- Tạo
fewestvớiamount + 1phần tử, tất cả đều được đặt thành giá trị đánh dấuamount + 1, rồi đặtfewest[0]thành 0. - Với mỗi tổng
ttừ 1 đếnamount, xét từng đồng xucsao choc ≤ t. - Nếu
fewest[t-c] + 1nhỏ hơnfewest[t], hãy lưu giá trị đó vàofewest[t]. - Sau vòng lặp, trả về -1 nếu
fewest[amount]vẫn chứa giá trị đánh dấu, nếu không thì trả vềfewest[amount].
def coinChange(coins, amount):
impossible = amount + 1
fewest = [0] + [impossible] * amount
for total in range(1, amount + 1):
for coin in coins:
if coin <= total and fewest[total - coin] + 1 < fewest[total]:
fewest[total] = fewest[total - coin] + 1
return fewest[amount] if fewest[amount] != impossible else -1
Lỗi thường gặp và trường hợp biên
- Chọn đồng xu có mệnh giá lớn nhất trước. Với các đồng xu mệnh giá 3 và 5, số tiền cần đổi là 9, cách này lấy đồng 5 và đồng 3, rồi mắc kẹt với số tiền 1 và trả về -1, trong khi 3 + 3 + 3 thì đổi được.
- Dùng số nguyên lớn nhất làm dấu đánh dấu. Cộng thêm 1 vào số đó sẽ gây tràn số thành số âm, rồi số này thắng mọi phép so sánh. Hãy dùng
amount + 1. - Cộng thêm 1 vào ngõ cụt. Một nhánh trả về -1, cộng với đồng xu bạn đã dùng, sẽ thành 0 và thắng mọi phép so sánh. Bỏ qua kết quả -1.
- Đệ quy sâu
amountcấp. Với đồng xu mệnh giá 1 và số tiền10^4, Python dừng ở giới hạn mặc định 1000 cấp, còn JavaScript, Dart, Ruby và R cũng hết ngăn xếp. - Đọc
fewest[t-c]với một đồng xu có mệnh giá lớn hơnt, tức là vị trí nằm trước đầu bảng.
Câu hỏi thường gặp3
Tại sao cách tiếp cận tham lam thất bại với bài toán đổi tiền?
Chọn đồng xu lớn nhất có thể dùng chỉ an toàn với một số hệ thống tiền xu, chẳng hạn như hầu hết các loại tiền tệ hiện nay. Với các đồng xu mệnh giá 1, 3 và 4, cách này cần ba đồng xu để trả 6 thay vì hai đồng, còn với các đồng xu mệnh giá 3 và 5 thì không thể trả đúng 9. Quy hoạch động so sánh mọi lựa chọn, nên không hệ thống tiền xu nào đánh lừa được nó.
Độ phức tạp thời gian của bài toán đổi tiền là gì?
Lời giải bằng quy hoạch động cần thời gian O(amount × coins) và không gian O(amount): mỗi giá trị tiền có một ô trong bảng, và với mỗi ô, chương trình kiểm tra từng đồng xu. Đệ quy thông thường không có ghi nhớ có độ phức tạp tăng theo hàm mũ của số tiền.
Với bài toán đổi tiền, cách tiếp cận từ trên xuống hay từ dưới lên tốt hơn?
Cả hai đều thực hiện cùng lượng công việc O(amount × coins). Đệ quy từ trên xuống có thể lồng sâu đến bằng số tiền cần đổi, khiến ngăn xếp lời gọi bị tràn với 10^4 trong một số ngôn ngữ. Cách từ dưới lên điền bảng bằng vòng lặp, nên không bị giới hạn độ sâu và là lựa chọn an toàn hơn trong buổi phỏng vấn.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def coinChange(coins, amount):
# Viết code tại đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
coins = [2, 5, 10] amount = 27
Đầu ra mong đợi
4