小学生都能看懂的题解 | #兑换零钱(一)#

我们可以通过动态规划来解决这个问题，目标是找到组成指定金额 aim 的最少货币数。我们将利用一个动态规划数组 dp 来存储每个金额对应的最小货币数量。

动态规划思路

1. 定义状态：

   • 定义一个数组 dp，其中 dp[i] 表示组成金额 i 所需的最少货币数。

2. 初始化：

   • dp[0] = 0，表示金额为 0 时不需要任何货币。
   • 对于其他金额，初始值设置为一个很大的数（比如 Integer.MAX_VALUE），表示暂时无法组成这些金额。

3. 状态转移：

   • 对于每种货币面值 coin，我们遍历 dp 数组从 coin 到 aim，更新 dp[i]：
     • 如果使用当前的面值 coin，那么可以通过 dp[i - coin] + 1 来更新 dp[i]，意思是我们需要再加上 1 张当前面值的货币。

4. 结果判断：

   • 如果 dp[aim] 仍然是初始的很大数值，说明无法组成 aim，返回 -1。
   • 否则，返回 dp[aim] 的值。

代码实现

下面是完整的 Java 代码实现：

public class Solution {
    public int minCoins(int[] arr, int aim) {
        // 边界情况：如果 aim 为 0，则需要 0 张货币
        if (aim == 0) {
            return 0;
        }
        
        // 创建 DP 数组，长度为 aim + 1
        int[] dp = new int[aim + 1];
        
        // 初始化 DP 数组
        for (int i = 1; i <= aim; i++) {
            dp[i] = Integer.MAX_VALUE; // 设置为一个很大的数，表示不可达
        }

        // 动态规划填充 DP 数组
        for (int coin : arr) {
            for (int i = coin; i <= aim; i++) {
                if (dp[i - coin] != Integer.MAX_VALUE) { // 检查是否可达
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1); // 更新最小货币数
                }
            }
        }

        // 返回结果，如果无法组成 aim 则返回 -1
        return dp[aim] == Integer.MAX_VALUE ? -1 : dp[aim];
    }
}

代码解析

1. public int minCoins(int[] arr, int aim)：方法接受一个货币面值的数组 arr 和目标金额 aim。

2. 边界检查：

   • 如果 aim 是 0，直接返回 0，因为不需要任何货币。

3. 创建和初始化 dp 数组：

   • dp[0] 默认是 0，表示组成金额 0 的最小货币数。
   • 其他金额初始化为 Integer.MAX_VALUE，表示初始时无法达到这些金额。

4. 动态规划逻辑：

   • 对每个面值 coin，遍历 dp 数组更新对应的值。
   • 如果 dp[i - coin] 不是不可达的（不等于 Integer.MAX_VALUE），就更新 dp[i]。

5. 结果判断：

   • 最后，如果 dp[aim] 仍为不可达的状态，返回 -1，否则返回 dp[aim]。

时间复杂度和空间复杂度

• 时间复杂度：O(n * aim)，其中 n 是数组的大小，aim 是目标金额。我们需要对每个面值进行遍历，同时更新 aim 的每个可能的值。
• 空间复杂度：O(aim)，使用了一个数组 dp 来存储从 0 到 aim 的解码结果。

示例运行

1. 输入 arr = [5, 2, 3] 和 aim = 20：

   • 可能的组合是：5 + 5 + 5 + 5，或者用其他方式组合，总共需要 4 张货币。
   • 输出 4。

2. 输入 arr = [5, 2, 3] 和 aim = 0：

   • 不需要任何货币。
   • 输出 0。

3. 输入 arr = [3, 5] 和 aim = 2：

   • 无法组成 2，所以返回 -1。