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. The solution uses dynamic programming to efficiently compute the result.
Approach
The key idea is to use dynamic programming (DP) where dp[i] represents the minimum number of coins needed to make the amount i. Here's the step-by-step approach:
-
Initialization:
- Create a DP array
dpof sizeamount + 1initialized to a value larger than the maximum possible number of coins (e.g.,amount + 1). This ensures that any unreachable amount remains marked as a large value. - Set
dp[0] = 0because zero coins are needed to make the amount 0.
- Create a DP array
-
DP Transition:
- For each amount from 1 to the target amount:
- For each coin denomination:
- If the coin value is less than or equal to the current amount, update
dp[i]to the minimum of its current value ordp[i - coin] + 1(using the current coin to make the amounti).
- For each amount from 1 to the target amount:
-
Result:
- If
dp[amount]remains larger than the target amount, it means the amount cannot be formed with the given coins, so return-1. Otherwise, returndp[amount].
- If
Solution Code
def coinChange(coins, amount):
max_coins = amount + 1
dp = [max_coins] * (amount + 1)
dp[0] = 0 # Base case: 0 coins needed to make amount 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != max_coins else -1
Explanation
- Initialization: The DP array starts with
max_coins(amount +1) to indicate that initially, all amounts are unreachable except 0. - DP Transition: For each amount, we check all coins. If a coin can contribute to the current amount, we update the DP value to the minimum number of coins needed.
- Result Check: After filling the DP array, if the target amount's value is still
max_coins, it means we can't form the amount with the given coins, so return-1. Otherwise, return the value atdp[amount].
This approach efficiently computes the solution with a time complexity of *O(amount number of coins) and space complexity of O(amount)**, which is optimal for typical problem constraints.
Examples:
- For
coins = [1,2,5]andamount =11, the result is3(5+5+1). - For
coins = [2]andamount=3, the result is-1(unreachable). - For
coins = [1]andamount=5, the result is5(five 1s).
This solution handles all edge cases and provides the correct minimum number of coins for the given problem.


作者声明:本文包含人工智能生成内容。