题解 | 兑换零钱(一)

1、解题思路

1. 动态规划：定义 dp[i] 为组成金额 i 所需的最少货币数量。初始条件： dp[0] = 0，表示组成金额 0 不需要任何货币。其他 dp[i] 初始化为 INT_MAX 或 aim + 1，表示暂时无法组成。状态转移方程： 对于每个货币面值 coin ，遍历所有金额 i 从 coin 到 aim ： dp[i] = min(dp[i], dp[i - coin] + 1)。
2. 边界条件：如果 aim 为 0，直接返回 0。如果 dp[aim] 仍为初始值，返回 -1。
3. 优化：使用一维数组 dp，空间复杂度为 O(aim)。先对货币面值排序，可以提前终止某些循环。

2、代码实现

C++

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型vector the array
     * @param aim int整型 the target
     * @return int整型
     */
    int minMoney(vector<int>& arr, int aim) {
        // write code here
        if (aim == 0) {
            return 0;
        }

        vector<int> dp(aim + 1, aim + 1);
        dp[0] = 0;  // 金额为 0 时需要 0 张货币

        for (int coin : arr) {
            for (int i = coin; i <= aim; ++i) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }

        return dp[aim] > aim ? -1 : dp[aim];
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney (int[] arr, int aim) {
        // write code here
        if (aim == 0) return 0;
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, aim + 1); // 初始化为 aim + 1，表示不可达
        dp[0] = 0; // 金额为 0 时需要 0 张货币
        for (int coin : arr) {
            for (int i = coin; i <= aim; ++i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[aim] > aim ? -1 : dp[aim];
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        if aim == 0:
            return 0
        dp = [aim + 1] * (aim + 1)  # 初始化为 aim + 1，表示不可达
        dp[0] = 0  # 金额为 0 时需要 0 张货币
        for coin in arr:
            for i in range(coin, aim + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[aim] if dp[aim] <= aim else -1

3、复杂度分析

• 时间复杂度：O(n × aim)，其中 n 是货币面值的种类数。
• 空间复杂度：O(aim)，用于存储 dp 数组。