每日一题——兑换零钱(一)

@toc

题目描述

给定一个数组 arr，数组中的每个值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张。再给定一个目标金额 aim，要求找出组成 aim 的最少货币数。如果无法组成 aim，则返回 -1。

数据范围：

数组大小满足 (0 \leq n \leq 10000)数组中每个数字满足 (0 < val \leq 10000)目标金额满足 (0 \leq aim \leq 5000)

要求：

时间复杂度 (O(n \times aim))空间复杂度 (O(aim)) 示例 示例1

输入：

[5, 2, 3], 20

返回值：

4

说明：

使用 4 张货币（5 + 5 + 5 + 5）可以组成 20。 示例2

输入：

[5, 2, 3], 0

返回值：

0

说明：

目标金额为 0，不需要任何货币。 示例3

输入：

[3, 5], 2

返回值：

-1

说明：

无法用给定的货币组成 2。

---

参考视频 题解 动态规划

我们可以使用动态规划来解决这个问题。设 dp[i] 表示组成金额 i 所需的最少货币数。状态转移方程如下：

对于每个金额 i，遍历所有货币面值 arr[j]。如果 i >= arr[j]，则 dp[i] = min(dp[i], dp[i - arr[j]] + 1)。

边界条件：

dp[0] = 0，表示组成金额 0 不需要任何货币。其他 dp[i] 初始化为一个较大的值（如 5001），表示暂时无法组成该金额。 代码实现 #include <stdio.h> #include <stdlib.h> /** * 动态规划求解最少货币数 * * @param arr int整型一维数组，表示货币的面值 * @param arrLen int，表示货币数组的长度 * @param aim int整型，表示目标金额 * @return int整型，表示组成目标金额的最少货币数，如果无法组成则返回-1 */ int minMoney(int* arr, int arrLen, int aim) { // 分配动态规划数组，dp[i] 表示组成金额 i 所需的最少货币数 int* dp = (int*)malloc((aim + 1) * sizeof(int)); if (dp == NULL) { printf("Memory allocation failed\n"); exit(1); } // 初始化动态规划数组，将所有值设置为一个较大的数（5001，因为题目中 aim 最大为 5000） for (int i = 0; i <= aim; i++) { dp[i] = 5001; } // 组成金额 0 所需的货币数为 0 dp[0] = 0; // 动态规划计算每个金额的最少货币数 for (int i = 1; i <= aim; i++) { for (int j = 0; j < arrLen; j++) { // 如果当前金额 i 大于等于货币面值 arr[j],以防止dp[i - arr[j]]越界 if (i >= arr[j]) { // 如果 dp[i - arr[j]] 是有效的（不是初始值 5001） if (dp[i - arr[j]] != 5001) { // 更新 dp[i] 为 dp[i - arr[j]] + 1 和当前 dp[i] 的最小值 dp[i] = (dp[i] < dp[i - arr[j]] + 1) ? dp[i] : dp[i - arr[j]] + 1; } } } } // 如果 dp[aim] 仍然是初始值 5001，表示无法组成金额 aim，返回 -1 int result = (dp[aim] == 5001) ? -1 : dp[aim]; // 释放动态规划数组 free(dp); // 返回结果 return result; } int main() { int arr[] = {5, 2, 3}; // 货币面值数组 int arrLen = 3; // 货币面值数组的长度 int aim = 20; // 目标金额 int result = minMoney(arr, arrLen, aim); // 调用函数计算最少货币数 printf("Minimum number of coins: %d\n", result); // 打印结果 return 0; } 复杂度分析 时间复杂度：(O(n \times aim))，其中 (n) 是货币数组的长度，aim 是目标金额。我们需要遍历每个金额和每种货币面值。空间复杂度：(O(aim))，用于存储动态规划数组 dp。

---

总结

本题通过动态规划的方法，将问题分解为子问题，逐步求解。通过状态转移方程，我们可以高效地计算出组成目标金额的最少货币数。如果无法组成目标金额，则返回 -1。