优化递归算法：解决有限硬币凑数问题

问题描述：有限硬币凑数

假设我们有一组不同面额的硬币，每种面额只有一枚。我们的任务是判断是否能够从这组硬币中选出若干枚，使其总和恰好等于一个给定的目标金额。例如，给定硬币面额 [1, 5, 16] 和目标金额 6，我们可以选择 1 和 5 凑成 6，因此结果为真。

初始递归尝试及问题分析

一种直观的递归思路是，遍历所有可用的硬币。对于每一枚硬币，我们尝试将其从集合中移除，并递归地判断剩余硬币能否凑成 目标金额 - 当前硬币面额。如果目标金额恰好为零，则说明找到了一个组合；如果目标金额变为负数或硬币用尽但目标金额不为零，则说明此路径不可行。

以下是初始代码实现的一个示例：

boolean go(int[] coins, int goal) {
  boolean ans = false;
  // 基本情况：目标金额为0，成功
  if (goal == 0) {
    return true;
  } else if (goal < 0) { // 基本情况：目标金额为负数，失败
    return false;
  }

  // 遍历所有硬币
  for (int i = 0; i < coins.length && (!ans); i++) {
    if (goal >= coins[i]) {
      // 创建一个新数组，移除当前硬币
      int[] red = new int[coins.length - 1];
      int it = 0;
      for (int x = 0; x < coins.length; x++) {
        if (!(i == x)) {
          // 错误所在：这里应该复制 coins[x]，而不是 coins[i]
          red[it] = coins[i]; // 这一行是错误的根源
          it += 1;
        }
      }
      // 递归调用，目标金额减去当前硬币面额
      ans = go(red, goal - coins[i]);
    }
  }
  return ans;
}

这段代码在某些测试用例中会产生错误。例如，对于硬币 [111, 1, 2, 3, 9, 11, 20, 30] 和目标金额 8，它错误地返回 true，而正确结果应为 false。

关键错误定位与解析

问题的核心在于数组 red 的复制逻辑。在内部循环中，当试图将 coins 数组中除 coins[i] 以外的元素复制到 red 数组时，代码错误地写成了 red[it] = coins[i]。这意味着无论 x 是什么，它都会将 coins[i]（即当前被“移除”的硬币）的值复制到 red 数组中，而不是将 coins[x]（即其他未被移除的硬币）的值复制进去。

正确的复制方式应该是 red[it] = coins[x]，以确保 red 数组包含的是除了 coins[i] 之外的所有硬币。这个错误导致 red 数组的内容不正确，从而使后续的递归调用基于错误的数据进行计算。

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

为了避免复杂的数组复制操作并提高代码的清晰度，我们可以采用一种更优雅的递归策略。对于当前考虑的硬币 coins[0]（假设我们总是处理数组的第一个元素），我们只有两种选择：

Tanka

具备AI长期记忆的下一代团队协作沟通工具

下载

1. 不使用当前硬币 coins[0]： 这种情况下，我们递归地在剩余的硬币 coins[1...n-1] 中寻找目标金额 goal。
2. 使用当前硬币 coins[0]： 这种情况下，我们递归地在剩余的硬币 coins[1...n-1] 中寻找目标金额 goal - coins[0]。

只要这两种情况中的任何一种能够成功凑出目标金额，那么总的结果就是 true。

优化代码实现

基于“选择与不选择”的策略，我们可以得到以下更简洁、高效的递归实现：

import java.util.Arrays; // 需要导入 Arrays 类

boolean go(int[] coins, int goal) {
    // 基本情况 1：目标金额为0，说明已成功凑齐
    if (goal == 0) {
        return true;
    }
    // 基本情况 2：
    // a) 硬币已用尽，但目标金额不为0，说明无法凑齐
    // b) 目标金额为负数，说明当前路径选择的硬币面额过大，无法凑齐
    else if (coins.length == 0 || goal < 0) {
        return false;
    }
    // 递归步骤
    else {
        // 创建一个新数组，包含除第一个硬币外的所有硬币
        int[] tailOfCoins = Arrays.copyOfRange(coins, 1, coins.length);

        // 两种可能性：
        // 1. 不使用当前硬币 coins[0]：在剩余硬币中寻找目标金额 goal
        // 2. 使用当前硬币 coins[0]：在剩余硬币中寻找目标金额 goal - coins[0]
        return go(tailOfCoins, goal) || go(tailOfCoins, goal - coins[0]);
    }
}

代码解析

• 基本情况 (Base Cases):
  • if (goal == 0): 这是成功的终止条件。如果目标金额已经降到 0，说明我们找到了一种组合方式。
  • else if (coins.length == 0 || goal
  • coins.length == 0: 如果所有硬币都已考虑完毕，但 goal 仍然不为 0，则无法凑齐。
  • goal

时间复杂度考量

这种优化后的递归方法虽然仍然是指数级的（因为它会探索所有可能的组合），但它避免了在每次递归调用中循环遍历数组并重新构建新数组的开销。Arrays.copyOfRange 操作本身会产生一个新的数组副本，其时间复杂度为 O(N)，其中 N 是当前数组的长度。然而，由于我们每次只处理一个硬币并将其从考虑范围中移除，相比于在循环中多次创建新数组，这种方式通常更为高效且代码更简洁。对于实际应用中可能出现的性能瓶颈，可以考虑使用动态规划（背包问题变种）来进一步优化，将其时间复杂度降低到多项式级别。

注意事项与总结

• 数组不可变性： 在递归中传递数组时，为了避免副作用，通常会创建数组的副本。Arrays.copyOfRange 是一个方便且安全的方法。
• 基本情况的重要性： 正确定义递归的基本情况是避免无限递归和确保正确结果的关键。
• 选择与不选择模式： 许多组合问题都可以通过这种“选择与不选择”的递归模式来解决，它能清晰地分解问题，并避免复杂的循环逻辑。
• 效率考量： 尽管递归解决方案简洁优雅，但对于大规模输入，其指数级的时间复杂度可能成为瓶颈。在这种情况下，应考虑使用动态规划等优化技术。

通过理解并应用这种优化后的递归策略，我们可以更准确、更高效地解决有限硬币凑数问题，同时避免常见的编程陷阱。