To solve this problem, we need to determine the minimum number of coins required to make a given amount using a set of coin denominations. If it's impossible to make the amount with the given coins, we should return -1.
Approach
The problem can be efficiently solved using dynamic programming (DP). Here's the step-by-step approach:
-
DP Array Initialization:
- We create a DP array
dpwheredp[i]represents the minimum number of coins needed to make the amounti. - Initialize
dpwith a value larger than the maximum possible coins (e.g.,float('inf')orm+1). This ensures that any unreachable amount remains marked as impossible initially. - Set
dp[0] = 0because zero coins are needed to make the amount 0.
- We create a DP array
-
Filling the DP Array:
- For each coin denomination, iterate over all amounts from the coin value to the target amount
m. - For each amount
j, updatedp[j]to the minimum value between its current value anddp[j - coin] + 1(using the current coin adds one more coin to the solution forj - coin).
- For each coin denomination, iterate over all amounts from the coin value to the target amount
-
Result Check:
- If
dp[m]remains larger thanm(orinf), it means the target amountmcannot be formed with the given coins, so return-1. - Otherwise, return
dp[m]as the minimum number of coins.
- If
Solution Code
n, m = map(int, input().split())
coins = list(map(int, input().split()))
# Initialize DP array
dp = [float('inf')] * (m + 1)
dp[0] = 0
# Fill DP array
for coin in coins:
for j in range(coin, m + 1):
dp[j] = min(dp[j], dp[j - coin] + 1)
# Determine result
print(dp[m] if dp[m] != float('inf') else -1)
Explanation
- Initialization: The DP array starts with
float('inf')to indicate that initially, all amounts are unreachable except0. - DP Transition: For each coin, we check if using that coin reduces the number of coins needed for each amount. This is done by comparing the current value of
dp[j]with the value obtained by adding one coin to the solution ofj - coin. - Result: The final check ensures we handle cases where the target amount is unreachable (return
-1) or return the minimum coins if reachable.
This approach efficiently computes the solution with a time complexity of O(n*m), where n is the number of coin denominations and m is the target amount, making it suitable for typical input sizes.
作者声明:本文包含人工智能生成内容。