c语言设计算法找零钱

设计算法找零钱的思路如下：

1. 定义一个数组 coins 存储所有可用的硬币面值，假设为 [1, 5, 10, 25]，并定义一个变量 amount 表示需要找的总金额。
2. 初始化一个长度为 amount+1 的数组 dp，dp[i] 表示找 i 元钱需要的最少硬币数。
3. 将 dp 数组全部初始化为正无穷大，除了 dp = 0。
4. 遍历 coins 数组，对于每个硬币面值 coin，从 coin 到 amount 遍历 dp 数组，更新 dp[j] = min(dp[j], dp[j-coin]+1)。

最终 dp[amount] 即为找零所需的最少硬币数。

C语言代码实现如下：

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

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

int coinChange(int* coins, int coinsSize, int amount){
    int dp[amount+1];
    for (int i = 0; i <= amount; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    for (int i = 0; i < coinsSize; i++) {
        for (int j = coins[i]; j <= amount; j++) {
            if (dp[j-coins[i]] != INT_MAX) {
                dp[j] = min(dp[j], dp[j-coins[i]]+1);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    int coins[] = {1, 5, 10, 25};
    int coinsSize = sizeof(coins) / sizeof(int);
    int amount = 41;
    int result = coinChange(coins, coinsSize, amount);
    printf("需要的最少硬币数为：%d\n", result);
    return 0;
}