用c语言动态规划法解决找零钱问题

动态规划法是一种常用的解决找零钱问题的算法。下面是用C语言实现的动态规划法解决找零钱问题的代码：

#include <stdio.h>

#define INF 0x3f3f3f3f

// coins为硬币面值，n为硬币种类数，k为要找的零钱数
int dp(int coins[], int n, int k) {
    int f[k+1];
    f[0] = 0;
    for (int i = 1; i <= k; i++) {
        f[i] = INF;
        for (int j = 0; j < n; j++) {
            int c = coins[j];
            if (i >= c && f[i-c] != INF && f[i-c]+1 < f[i]) {
                f[i] = f[i-c] + 1;
            }
        }
    }
    return f[k];
}

int main() {
    int coins[] = {1, 3, 5};
    int n = sizeof(coins) / sizeof(coins[0]);
    int k = 11;
    int ans = dp(coins, n, k);
    printf("最少需要%d个硬币\n", ans);
    return 0;
}

这里定义了一个`dp`函数来解决找零钱问题，输入参数为硬币面值数组`coins`、硬币种类数`n`和要找的零钱数`k`。函数返回值为最少需要的硬币数。

在函数内部，首先定义一个长度为`k+1`的数组`f`，并将`f[0]`初始化为0。然后开始循环，从`f[1]`到`f[k]`依次计算出最少需要的硬币数。

对于每一个`f[i]`，我们需要遍历硬币面值数组`coins`，找到一个小于等于`i`的硬币面值`c`。如果`i-c`是可以被拼成的，并且`f[i-c]+1`比当前的`f[i]`更小，那么就更新`f[i]`的值。

最终，`f[k]`的值就是最少需要的硬币数。