头歌c语言找零问题代码

在C语言中，解决找零问题通常使用动态规划的思想。这里以找零1元、5元和10元硬币为例，编写一个简单的函数。首先定义一个大小等于需要找零金额+1的数组`change[]`，然后初始化，设置大于当前找零需求的元素为0，接着进行状态转移。

#include <stdio.h>

int coinChange(int coins[], int m, int n) {
    int change[n + 1]; // 存储找到的最小硬币组合数
    memset(change, 0, sizeof(change)); // 初始化所有金额为0

    for (int amount = 1; amount <= n; amount++) { // 遍历找零金额
        for (int i = 0; i < m && coins[i] <= amount; i++) { // 检查是否有足够的硬币
            if (change[amount - coins[i]] != 0) // 如果可以组成，用这个硬币加上已知的找零组合
                change[amount] = min(change[amount], change[amount - coins[i]] + 1); // 更新最少硬币数
        }
        if (change[amount] == 0) return -1; // 如果无法组成，返回-1表示无解
    }

    return change[n]; // 返回最小硬币组合数
}

// 辅助函数，获取两个整数之间的最小值
int min(int a, int b) {
    return a < b ? a : b;
}

int main() {
    int coins[] = {1, 5, 10};
    int m = sizeof(coins) / sizeof(coins[0]);
    int n = 18; // 需要找零的金额
    int result = coinChange(coins, m, n);
    printf("最小硬币组合数: %d\n", result);

    return 0;
}

这个代码实现了找零问题的解决方案，输入是一组硬币面额和需要找零的金额。运行时会打印出最小的硬币组合数。注意，这个版本假设有足够的硬币，实际应用中可能需要额外处理这种情况。