To solve this problem, we need to determine the number of ways to make change for a given amount using coins of denominations 1, 5, 10, and 25. This is a classic dynamic programming problem where we build up the solution by considering each coin denomination and updating the number of ways to form each amount up to the target value.
Approach
- Dynamic Programming (DP) Setup: We use a DP array
dpwheredp[i]represents the number of ways to make the amounti. - Base Case:
dp[0] = 1because there is exactly one way to make the amount 0 (using no coins). - Iterate Over Coins: For each coin denomination, update the DP array from the coin value up to the target amount. This ensures we count all combinations without double-counting (since we process each coin once and build up the solution incrementally).
- Update DP Array: For each amount
jfrom the current coin value to the target, add the number of ways to makej - cointodp[j](since adding the current coin to those ways gives a new way to makej).
Solution Code
def count_change_ways(n):
coins = [1, 5, 10, 25]
dp = [0] * (n + 1)
dp[0] = 1 # Base case: one way to make 0 amount
for coin in coins:
for j in range(coin, n + 1):
dp[j] += dp[j - coin]
return dp[n]
# Example usage:
# print(count_change_ways(5)) # Output: 2
# print(count_change_ways(10)) # Output: 4
# print(count_change_ways(15)) # Output: 6
Explanation
- Base Case:
dp[0] = 1is essential because it allows us to start building the solution for larger amounts. - Coin Processing: By iterating over each coin and updating the DP array from the coin value upwards, we ensure that each combination is counted exactly once. For example, when processing the coin 5, we add the ways to make
j-5todp[j], which includes all combinations that use the coin 5. - Efficiency: The time complexity is
O(n * k)wherenis the target amount andkis the number of coin denominations (4 here). This is efficient even for large values ofn(e.g., up to 10,000) because the number of coins is small.
This approach correctly computes the number of combinations to make the desired amount using the given coin denominations. It is optimal and easy to understand, making it a standard solution for this type of problem.


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