递归算法实践：有限硬币目标和判定及其优化

问题描述：有限硬币凑和

在计算机科学中，我们经常会遇到需要从给定集合中选择元素以达到特定目标的问题。其中一个经典变种是“有限硬币凑和问题”：给定一组硬币面额（例如，1元、5元、16元），其中每种面额的硬币只有一枚，我们需要判断是否能从这组硬币中选出若干枚，使其总和恰好等于一个目标金额。这里的关键在于“有限”二字，即每种硬币最多只能使用一次。这与经典的“硬币找零问题”（硬币可以无限次使用）有所不同，对递归的设计提出了特定的要求。

递归初探与常见陷阱

解决这类问题，递归是一个自然的选择。其基本思路是：对于每个硬币，我们都可以选择使用它或不使用它，然后将问题简化为子问题。然而，在实际实现中，尤其是在处理硬币集合时，很容易引入错误或导致效率低下。

数组复制错误分析

一个常见的陷阱是在递归调用中创建新的硬币子集时，错误地复制了数组元素。例如，在尝试构建一个排除当前硬币的新数组时，如果使用了类似red[it] = coins[i]的逻辑，但实际上期望复制的是coins[x]（即原始数组中非当前硬币的其他元素），就会导致新数组的内容不正确。这种细微的错误可能导致某些测试用例返回意料之外的结果，例如在给定硬币[111, 1, 2, 3, 9, 11, 20, 30]和目标金额8时，本应返回false，却错误地返回true。这通常是因为在构建子数组时，不小心重复包含了某些硬币，或者遗漏了其他硬币。

效率考量

除了逻辑错误，初学者还可能在递归循环中频繁地创建新的硬币数组。如果在一个循环中迭代所有硬币，并且每次迭代都创建一个新的、稍小的数组传递给递归调用，这会带来显著的性能开销。每次数组复制都涉及内存分配和元素拷贝，当硬币数量较多时，这种操作会极大地拖慢程序的执行速度，导致时间复杂度居高不下。

优化后的递归策略：选择与不选择

为了解决上述问题，我们可以采用一种更简洁高效的递归策略，其核心思想是：对于当前处理的第一个硬币，我们有两种互斥的选择——要么使用它，要么不使用它。

钛投标

钛投标 | 全年免费 | 不限字数 | AI标书智写工具

157

查看详情

1. 不使用当前硬币: 如果我们选择不使用当前硬币，那么问题就变成了：在剩余的硬币中，能否凑成原始的目标金额？
2. 使用当前硬币: 如果我们选择使用当前硬币，那么问题就变成了：在剩余的硬币中，能否凑成目标金额减去当前硬币面额？

只要这两种情况中的任何一种能够成功（即返回true），那么原始问题就能被解决。

基线条件 (Base Cases)

为了确保递归能够正确终止，我们需要定义清晰的基线条件：

• 目标金额为 0: 如果目标金额已经变为 0，这意味着我们已经成功凑出了目标金额，此时返回true。
• 硬币用尽或目标金额为负: 如果我们已经没有硬币可以尝试了（coins.length == 0），或者在减去某个硬币后目标金额变为负数（goal < 0），这意味着我们无法凑出目标金额，此时返回false。

Java代码实现

下面是基于上述优化策略的Java代码实现：

import java.util.Arrays;

public class CoinSumSolver {

    /**
     * 使用递归判断给定有限硬币能否凑成目标金额。
     * 每种硬币只能使用一次。
     *
     * @param coins 硬币面额数组
     * @param goal 目标金额
     * @return 如果能凑成目标金额则返回 true，否则返回 false
     */
    public static boolean canMakeSum(int[] coins, int goal) {
        // 基线条件 1: 如果目标金额为 0，说明已经凑成，返回 true
        if (goal == 0) {
            return true;
        }

        // 基线条件 2: 如果没有硬币了，或者目标金额为负数（超出了），则无法凑成，返回 false
        if (coins.length == 0 || goal < 0) {
            return false;
        }

        // 获取当前处理的第一个硬币面额
        int currentCoin = coins[0];
        // 创建一个包含剩余硬币的新数组，使用 Arrays.copyOfRange 简化操作
        int[] remainingCoins = Arrays.copyOfRange(coins, 1, coins.length);

        // 递归调用：
        // 1. 不使用当前硬币：在剩余硬币中寻找目标金额
        // 2. 使用当前硬币：在剩余硬币中寻找目标金额减去当前硬币面额
        // 只要其中一种情况能成功，就返回 true
        return canMakeSum(remainingCoins, goal) || canMakeSum(remainingCoins, goal - currentCoin);
    }

    public static void main(String[] args) {
        // 测试用例
        int[] coins1 = {1, 5, 16};
        int goal1 = 6; // 1 + 5 = 6 -> true
        System.out.println("Coins: " + Arrays.toString(coins1) + ", Goal: " + goal1 + " -> " + canMakeSum(coins1, goal1)); // 预期: true

        int[] coins2 = {111, 1, 2, 3, 9, 11, 20, 30};
        int goal2 = 8; // 无法凑成 -> false
        System.out.println("Coins: " + Arrays.toString(coins2) + ", Goal: " + goal2 + " -> " + canMakeSum(coins2, goal2)); // 预期: false

        int[] coins3 = {1, 2, 3};
        int goal3 = 4; // 1 + 3 = 4 -> true
        System.out.println("Coins: " + Arrays.toString(coins3) + ", Goal: " + goal3 + " -> " + canMakeSum(coins3, goal3)); // 预期: true

        int[] coins4 = {10, 20, 30};
        int goal4 = 5; // 无法凑成 -> false
        System.out.println("Coins: " + Arrays.toString(coins4) + ", Goal: " + goal4 + " -> " + canMakeSum(coins4, goal4)); // 预期: false
    }
}

代码解析

• if (goal == 0): 这是最直接的成功条件。一旦目标金额降为 0，说明我们已经找到了一个有效的硬币组合。
• if (coins.length == 0 || goal < 0): 这是失败条件。coins.length == 0表示所有硬币都已尝试过，但仍未达到目标金额；goal < 0表示我们选择了某个硬币后，目标金额变得比 0 小，说明这个路径是无效的。
• int currentCoin = coins[0];: 每次递归调用都从当前硬币数组的第一个元素开始处理。
• int[] remainingCoins = Arrays.copyOfRange(coins, 1, coins.length);: 这一行是关键。它高效地创建了一个新数组，其中包含了除了第一个硬币之外的所有硬币。Arrays.copyOfRange方法比手动循环复制更加简洁和不易出错。
• return canMakeSum(remainingCoins, goal) || canMakeSum(remainingCoins, goal - currentCoin);: 这是递归的核心。
  • canMakeSum(remainingCoins, goal)：代表了“不使用currentCoin”的情况。我们继续在剩余的硬币中寻找原始的目标金额。
  • canMakeSum(remainingCoins, goal - currentCoin)：代表了“使用currentCoin”的情况。我们从目标金额中减去currentCoin的面额，然后继续在剩余的硬币中寻找新的目标金额。
  • ||操作符表示只要这两种可能性中的任何一种能够成功（返回true），那么整个表达式就返回true。

注意事项与进一步优化

1. 时间复杂度: 尽管上述优化后的递归代码在逻辑上更清晰，并且避免了错误的数组复制，但其时间复杂度仍然是指数级的，大约为 O(2^n)，其中 n 是硬币的数量。这是因为每个硬币都有“选择”或“不选择”两种路径，导致递归树呈指数级增长。对于硬币数量较大的情况，这种方法可能会非常慢。
2. 空间复杂度: 每次递归调用都会创建一个新的remainingCoins数组，这会导致额外的空间开销，其深度取决于硬币的数量。
3. 动态规划/记忆化搜索: 对于硬币数量和目标金额都较大的场景，更高效的解决方案通常是采用动态规划（Dynamic Programming）或记忆化搜索（Memoization）。这些方法通过存储和重用子问题的结果，避免了重复计算，可以将时间复杂度降低到 O(n * goal)，显著提高性能。然而，这超出了纯粹递归的范畴。
4. 硬币顺序: 在此特定解法中，硬币数组的初始顺序不影响最终结果，但会影响递归树的遍历路径和特定时刻的计算。

总结

通过本教程，我们深入探讨了如何使用递归算法解决有限硬币凑和问题。我们首先分析了初学者在实现中可能遇到的数组复制错误和效率瓶颈，随后提出并实现了一种更健壮、更易于理解的“选择或不选择”递归策略。该策略通过明确的基线条件和高效的数组子集创建（利用Arrays.copyOfRange），提供了一个优雅的解决方案。尽管这种纯递归方法在处理大规模问题时存在性能限制，但它为理解和构建更复杂的动态规划解决方案奠定了基础。在实际应用中，对于性能要求较高的场景，应考虑采用动态规划等优化技术。

以上就是递归算法实践：有限硬币目标和判定及其优化的详细内容，更多请关注php中文网其它相关文章！