钞票和硬币问题用c语言怎么写

钞票和硬币问题是一个经典的动态规划问题，通常用于教学如何解决背包问题。这个题目通常涉及给定一些面额的硬币和一张最大金额，问有多少种组合可以凑出这个金额。以下是使用 C 语言的基本思路：

#include <stdio.h>

int coinChange(int coins[], int n, int target) {
    // 初始化一个一维数组dp[]，存储从0到target的最大硬币组合数
    int dp[target + 1];
    memset(dp, 0, sizeof(dp));

    // dp[0]表示没有钱时有0种组合
    dp[0] = 1;

    // 遍历所有可能的硬币面额
    for (int i = 0; i < n; ++i) {
        // 对于每个硬币面额，尝试将它加入当前组合并更新剩余金额的解决方案
        for (int j = coins[i]; j <= target; ++j) {
            dp[j] += dp[j - coins[i]];  // 动态规划核心：如果能用i号硬币组成，则在剩下的金额里加1
        }
    }

    return dp[target];  // 返回目标金额下的组合数
}

int main() {
    int coins[] = {1, 2, 5};  // 假设有1元、2元、5元硬币
    int n = sizeof(coins) / sizeof(coins[0]);  // 硬币总数
    int target = 11;  // 目标金额

    int result = coinChange(coins, n, target);
    if (result > 0)
        printf("可以找到 %d 种硬币组合。\n", result);
    else
        printf("无法组成目标金额。\n");

    return 0;
}