动态规划找零问题c语言代码
时间: 2023-07-23 17:13:56 浏览: 35
下面是一个基于动态规划的找零问题的 C 语言代码示例:
```c
#include <stdio.h>
int min(int a, int b) {
return (a < b) ? a : b;
}
int findMinCoins(int coins[], int n, int amount) {
int dp[amount + 1];
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
dp[i] = INT_MAX;
}
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < n; j++) {
if (coins[j] <= i) {
int sub_res = dp[i - coins[j]];
if (sub_res != INT_MAX && sub_res + 1 < dp[i]) {
dp[i] = sub_res + 1;
}
}
}
}
return dp[amount];
}
int main() {
int coins[] = {1, 5, 10, 25};
int n = sizeof(coins) / sizeof(coins[0]);
int amount = 67;
printf("Minimum number of coins required to make change for %d: %d\n", amount, findMinCoins(coins, n, amount));
return 0;
}
```
这个代码使用了一个一维数组 `dp` 来保存每个金额所需要的最小硬币数。初始时,将 `dp[0]` 设置为 0,其他位置设置为正无穷。接着,对于每个金额 `i`,遍历硬币数组,如果当前硬币面值小于等于当前金额,就计算使用这个硬币后剩余金额所需要的最小硬币数,并将其加 1 作为当前金额所需的硬币数。最后返回 `dp[amount]` 即可。