Giả sử chúng ta có tiền xu có mệnh giá khác nhau (1,5,10,25) và tổng số tiền là tiền. Chúng ta phải xác định một hàm để tính số lượng coin ít nhất mà chúng ta cần để tạo nên số tiền đó. Vì vậy, nếu đầu vào là 64, đầu ra là 7. Giá trị này được hình thành bằng cách sử dụng 25 + 25 + 10 + 1 + 1 + 1 + 1 =64.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- nếu số tiền =0, thì trả về 0
- nếu số tiền tối thiểu> số tiền, thì trả về -1
- xác định một mảng được gọi là dp, có kích thước số tiền là + 1 và điền vào mảng này với -1
- cho tôi trong mảng tiền xu trong phạm vi
- if i> length of dp - 1, then bỏ qua phần tiếp theo, chuyển sang phần tiếp theo
- dp [i]:=1
- cho j trong phạm vi i + 1 thành số tiền
- nếu dp [j - 1] =-1, thì bỏ qua phần tiếp theo, chuyển sang lần lặp tiếp theo
- ngược lại nếu dp [j] =-1 thì dp [j]:=dp [j - i] + 1
- nếu không thì dp [j]:=tối thiểu là dp [j] và dp [j - i] + 1
- trả lại dp [số tiền]
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution(object): def coinChange(self, amount): coins = [1,5,10,25] if amount == 0 : return 0 if min(coins) > amount: return -1 dp = [-1 for i in range(0, amount + 1)] for i in coins: if i > len(dp) - 1: continue dp[i] = 1 for j in range(i + 1, amount + 1): if dp[j - i] == -1: continue elif dp[j] == -1: dp[j] = dp[j - i] + 1 else: dp[j] = min(dp[j], dp[j - i] + 1) return dp[amount] ob1 = Solution() print(ob1.coinChange(64))
Đầu vào
64
Đầu ra
7