【动态规划入门--零钱兑换】C语言版

零钱兑换问题的动态规划解法（C语言实现）

零钱兑换问题是一个经典的动态规划问题，其核心在于通过组合不同面额的硬币，找到凑成目标金额所需的最少硬币数量。以下是该问题的详细解析和C语言实现。

1. 问题分析

目标：给定不同面额的硬币和一个总金额，计算凑成该金额所需的最少硬币数量。
约束：每种硬币的数量无限，若无法凑成目标金额，则返回-1。

2. 动态规划思路2.1 定义状态

dp数组：dp[i]表示凑成金额i所需的最少硬币数量。
初始化：dp[0] = 0（金额为0时无需硬币），其余dp[i]初始化为一个较大值（如amount + 1），便于后续比较。

2.2 状态转移方程

对于金额i，遍历所有硬币面额coin：

若coin <= i，则dp[i] = min(dp[i], dp[i - coin] + 1)。
解释：当前金额i的最优解可通过i - coin的最优解加上当前硬币得到。

2.3 边界条件

若dp[amount]未被更新（仍为初始值），说明无法凑成目标金额，返回-1。

3. C语言实现#include <stdio.h>#include <stdlib.h>int min(int a, int b) { return a < b ? a : b;}int coinChange(int* coins, int coinsSize, int amount) { int* dp = (int*)malloc((amount + 1) * sizeof(int)); dp[0] = 0; // 金额为0时无需硬币 // 初始化dp数组 for (int i = 1; i <= amount; i++) { dp[i] = amount + 1; // 初始化为不可达值 } // 动态规划填充dp数组 for (int i = 1; i <= amount; i++) { for (int j = 0; j < coinsSize; j++) { if (coins[j] <= i) { dp[i] = min(dp[i], dp[i - coins[j]] + 1); } } } int result = dp[amount] > amount ? -1 : dp[amount]; free(dp); // 释放动态分配的内存 return result;}int main() { int coins[] = {1, 2, 5}; int amount = 11; int coinsSize = sizeof(coins) / sizeof(coins[0]); int res = coinChange(coins, coinsSize, amount); printf("最少需要%d个硬币n", res); // 输出：3（5+5+1） return 0;}4. 代码解析

初始化：
dp[0] = 0：金额为0时无需硬币。
其余dp[i]初始化为amount + 1，表示初始不可达状态。
动态规划填充：
外层循环遍历金额1到amount。
内层循环遍历所有硬币面额，更新dp[i]为最小值。
结果处理：
若dp[amount]未被更新（仍为amount + 1），返回-1；否则返回dp[amount]。
内存管理：
使用malloc动态分配dp数组，最后通过free释放内存。

5. 示例验证

输入：coins = [1, 2, 5], amount = 11
输出：3（组合：5 + 5 + 1）
解释：
dp[1] = 1（硬币1）
dp[2] = min(dp[1]+1, dp[0]+1) = 1（硬币2）
dp[5] = 1（硬币5）
dp[11] = min(dp[10]+1, dp[9]+1, dp[6]+1) = 3（通过5+5+1得到）

6. 复杂度分析

时间复杂度：O(amount × coinsSize)，需遍历金额和硬币面额。
空间复杂度：O(amount)，用于存储dp数组。

7. 总结

动态规划通过将问题分解为子问题，逐步构建最优解，避免了重复计算。在零钱兑换问题中，通过合理定义状态和转移方程，能够高效地找到最优解。

您可能感兴趣问答

Collapsible

热门标签

热点问答