银币问题最少次数C语言

银币问题最少次数是指，假设有面值为 1 元、2 元、5 元的银币若干枚，现在需要找零 n 元，最少需要多少枚银币才能找完？

这个问题可以使用动态规划算法来解决。我们可以定义一个一维数组 dp，其中 dp[i] 表示找零 i 元所需的最少银币数量。具体步骤如下：

1. 初始化 dp 数组，将 dp[0] 设为 0，其余元素设为一个很大的数，比如 INT_MAX。
2. 枚举所有的面值，对于面值值为 coin 的银币，更新 dp 数组的值，即 dp[i] = min(dp[i], dp[i - coin] + 1)，其中 i >= coin。
3. 最终 dp[n] 的值即为所需的最少银币数量。

以下是 C 语言的代码实现：

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

#define MAX_N 1000   // 找零的最大金额
#define MAX_COINS 10 // 可用的银币面值数

int coins[MAX_COINS] = {1, 2, 5}; // 银币面值
int dp[MAX_N];                   // dp 数组

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

int main() {
    int n = 11; // 需要找零的金额
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = INT_MAX;
        for (int j = 0; j < MAX_COINS; j++) {
            if (i >= coins[j]) {
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    printf("找零 %d 元需要的最少银币数量为：%d\n", n, dp[n]);
    return 0;
}

输出结果为：

找零 11 元需要的最少银币数量为：3

即需要 3 枚银币才能找完 11 元。