Cho mảng mệnh giá tiền xu coins và số tiền amount. Tìm số đồng xu ít nhất cần dùng để tạo thành số tiền đó. Nếu không đổi được trả về -1.
Ví dụ: coins = [1, 2, 5], amount = 11 -> Output: 3 (5 + 5 + 1).
Định Dạng Đầu Vào (Input)
Dòng 1: coins
Dòng 2: amount
Dòng 2: amount
Định Dạng Đầu Ra (Output)
Số xu ít nhất hoặc -1
Ràng Buộc (Constraints)
1 <= coins.length <= 12, 0 <= amount <= 10^4
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[1, 2, 5]
11
Output:
3
Giải thích: 5 + 5 + 1
Ví dụ 2:
Input:
[2]
3
Output:
-1
Giải thích: Không đổi được
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Bottom-up DP O(amount * len(coins))
dp[i] = min(dp[i], dp[i - c] + 1)
Dữ liệu đầu vào (Input):
[1, 2, 5]
11
Kết quả kỳ vọng (Expected Output):
3
Dữ liệu đầu vào (Input):
[2]
3
Kết quả kỳ vọng (Expected Output):
-1
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
