Đề bài
Sử dụng bất kỳ số lượng nào của mỗi mệnh giá được cung cấp để tạo ra đúng số tiền. Đếm số cách kết hợp, không tính thứ tự: hai cách sắp xếp sử dụng cùng số lượng mỗi loại đồng xu được coi là một cách. Các mệnh giá là khác nhau và dương.
Cài đặt coin_sums(amount, coins).
Đầu vào
amount: Tổng số tiền cần tạo.
coins: Các mệnh giá khác nhau có sẵn.
Đầu ra
Trả về số lượng cách kết hợp không phân biệt thứ tự.
Ràng buộc
0 ≤ amount ≤ 200. Có từ 0 đến 10 mệnh giá khác nhau, mỗi mệnh giá từ 1 đến 200. Tất cả số lượng đều vừa với kiểu số nguyên có dấu 64-bit. Trường hợp amount = 0 có một cách duy nhất: không chọn đồng xu nào.
Ví dụ
Đầu vào:
coins = [1, 2]
amount = 4
Kết quả mong đợi:
expected = 3Đầu vào:
std::vector<long long> coins = {1, 2};
long long amount = 4;
Kết quả mong đợi:
long long expected = 3;Đầu vào:
long[] coins = new long[] {1, 2};
long amount = 4;
Kết quả mong đợi:
long expected = 3;Giải thích
Các cách kết hợp là bốn đồng 1, hai đồng 1 với một đồng 2, và hai đồng 2.
Đầu vào:
coins = [2]
amount = 3
Kết quả mong đợi:
expected = 0Đầu vào:
std::vector<long long> coins = {2};
long long amount = 3;
Kết quả mong đợi:
long long expected = 0;Đầu vào:
long[] coins = new long[] {2};
long amount = 3;
Kết quả mong đợi:
long expected = 0;Giải thích
Tổng các đồng xu mệnh giá 2 luôn là số chẵn, nên không thể tạo ra 3.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Thứ tự đồng xu không quan trọng, nên phải đếm theo mệnh giá chứ không theo hoán vị.
Gợi ý 2
Xây số cách cho từng số tiền dần dần, để mỗi đồng xu đóng góp vào mọi tổng có thể đạt được.
Gợi ý 3
Cẩn thận với số tiền 0, vì luôn có đúng một cách hợp lệ: không chọn đồng nào.
Độ phức tạp mong đợi
thời gian O(amount × number_of_coins), bộ nhớ phụ O(amount)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.