编辑代码

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int coinCollect(int coins[], int size, int target) {
    int dp[target + 1];
    dp[0] = 0;
    
    for (int i = 1; i <= target; i++) {
        dp[i] = INT_MAX;
        
        for (int j = 0; j < size; j++) {
            if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    
    return dp[target] == INT_MAX ? -1 : dp[target];
}

int main() {
    int coins[] = {1, 5, 10, 25}; // 硬币面值
    int size = sizeof(coins) / sizeof(coins[0]); // 硬币数量
    int target; // 目标金额

    printf("请输入目标金额：");
    scanf("%d", &target);
    
    int result = coinCollect(coins, size, target);
    
    if (result == -1) {
        printf("无法凑够目标金额\n");
    } else {
        printf("最少需要%d个硬币\n", result);
    }
    
    return 0;
}