本文深入解析零钱兑换算法问题，涵盖题目描述、数学建模及多种解法对比。核心采用动态规划解决完全背包问题，提供记忆化搜索、自底向上 DP 及 BFS 方案。详细分析时间空间复杂度，并通过代码实现展示状态转移方程。此外，探讨贪心策略局限性、边界条件处理及实际应用场景如金融支付与资源调度，为面试及工程实践提供参考。
题目描述：
给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
coins = [1, 2, 5], amount = 11 的所有可能组合：
- 11 = 1×11 (11 个硬币)
- 11 = 2×5 + 1×1 (6 个硬币)
- 11 = 5×2 + 1×1 (3 个硬币) ✓ 最优解
- 11 = 5×1 + 2×3 (4 个硬币)
coins = [2], amount = 3：
- 无法用面额为 2 的硬币组成金额 3
- 返回 -1
coins = [1], amount = 0：
- 金额为 0，不需要任何硬币
- 返回 0
coins 和目标金额 amount这是一个经典的整数线性规划问题：
min ∑(i=0 to n-1) x_i s.t. ∑(i=0 to n-1) x_i · c_i = S x_i ∈ N, ∀i ∈ [0, n-1]
其中：
这个问题本质上是一个完全背包问题：
如果已知组成金额 S - c_i 的最少硬币数量，那么组成金额 S 的最少数量就是 F(S - c_i) + 1。
计算 F(S) 时需要多次使用 F(S - c_i) 的值，存在大量重复计算。
F(0) = 0：金额为 0 时不需要硬币F(S) = -1：当无法组成金额 S 时// ❌ 贪心策略：总是选择最大的硬币面额
public int coinChangeGreedy(int[] coins, int amount) {
Arrays.sort(coins);
int count = 0;
for (int i = coins.length - 1; i >= 0; i--) {
count += amount / coins[i];
amount %= coins[i];
}
return amount == 0 ? count : -1;
}
反例验证：
coins = [1, 3, 4], amount = 6// ❌ 暴力递归（指数时间复杂度）
public int coinChangeBruteForce(int[] coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return -1;
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int subResult = coinChangeBruteForce(coins, amount - coin);
if (subResult != -1) {
minCoins = Math.min(minCoins, subResult + 1);
}
}
return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
}
问题：
// ❌ 忽略边界条件的错误实现
public int coinChangeWrong(int[] coins, int amount) {
int[] dp = new int[amount]; // 错误：应该是 amount+1
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
// 当 amount=0 时会出错
// ...
}
}
问题：
amount+1 而不是 amountamount=0 的特殊情况💡 关键洞察：零钱兑换问题的核心在于理解"当前状态依赖于所有可能的前驱状态"这一性质，这正是动态规划的典型应用场景。同时，要特别注意贪心策略在此类问题中的局限性！
核心思想：在递归的基础上，用缓存避免重复计算
算法步骤：
coinChangeHelper(amount)memo 缓存已计算的结果核心思想：从小到大计算每个金额的最少硬币数
状态定义：
dp[i] 表示组成金额 i 所需的最少硬币数量状态转移方程：
dp[i] = min(dp[i - coin] + 1)，其中 coin <= i边界条件：
dp[0] = 0amount + 1（表示不可达）核心思想：将问题建模为图的最短路径问题
核心思想：利用硬币系统的数学性质进行优化
public class Solution {
/**
* 记忆化搜索解法（自顶向下）
* 时间复杂度：O(amount × coins.length)
* 空间复杂度：O(amount)
*/
public int coinChange(int[] coins, int amount) {
if (amount < 1) {
return 0;
}
// memo[i] 表示组成金额 i 所需的最少硬币数
// memo[i-1] 对应金额 i（因为数组从 0 开始）
int[] memo = new int[amount];
return coinChangeHelper(coins, amount, memo);
}
private int coinChangeHelper(int[] coins, int amount, int[] memo) {
// 基础情况
if (amount < 0) {
return -1;
}
if (amount == 0) {
return 0;
}
// 检查缓存
if (memo[amount - 1] != 0) {
return memo[amount - 1];
}
int minCoins = Integer.MAX_VALUE;
// 尝试每种硬币
for (int coin : coins) {
int subResult = coinChangeHelper(coins, amount - coin, memo);
if (subResult >= 0 && subResult < minCoins) {
minCoins = subResult + 1;
}
}
// 缓存结果
memo[amount - 1] = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
return memo[amount - 1];
}
}
import java.util.Arrays;
public class Solution {
/**
* 动态规划解法（自底向上）
* 时间复杂度：O(amount × coins.length)
* 空间复杂度：O(amount)
*/
public int coinChange(int[] coins, int amount) {
// 特殊情况处理
if (amount == 0) {
return 0;
}
// dp[i] 表示组成金额 i 所需的最少硬币数
int[] dp = new int[amount + 1];
// 初始化：用 amount+1 表示不可达（比最大可能值还大）
Arrays.fill(dp, amount + 1);
dp[0] = 0; // 金额 0 需要 0 个硬币
// 自底向上计算
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
// 返回结果
return dp[amount] > amount ? -1 : dp[amount];
}
}
import java.util.*;
public class Solution {
/**
* BFS 解法（最短路径思想）
* 时间复杂度：O(amount × coins.length) - 最坏情况
* 空间复杂度：O(amount)
*/
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(0);
visited.add(0);
int level = 0;
while (!queue.isEmpty()) {
level++;
int size = queue.size();
// 处理当前层的所有节点
for (int i = 0; i < size; i++) {
int currentAmount = queue.poll();
// 尝试添加每种硬币
for (int coin : coins) {
int nextAmount = currentAmount + coin;
// 找到目标金额
if (nextAmount == amount) {
return level;
}
// 避免重复访问和超出范围
if (nextAmount < amount && !visited.contains(nextAmount)) {
visited.add(nextAmount);
queue.offer(nextAmount);
}
}
}
}
return -1;
}
}
import java.util.Arrays;
public class Solution {
/**
* 优化的动态规划（硬币面额排序）
* 时间复杂度：O(amount × coins.length)
* 空间复杂度：O(amount)
*/
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
// 排序硬币面额（可选优化）
Arrays.sort(coins);
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin > i) break; // 提前终止（因为已排序）
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
import java.util.Arrays;
public class Solution {
/**
* 空间优化版本（实际上无法进一步优化空间）
* 注意：完全背包问题通常无法优化到 O(1) 空间
* 时间复杂度：O(amount × coins.length)
* 空间复杂度：O(amount)
*/
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
// 由于需要访问任意位置的 dp 值，无法优化空间
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
// 完全背包：正向遍历
for (int i = coin; i <= amount; i++) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
让我们详细分析最常用的动态规划解法：
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // 初始化为不可达状态
dp[0] = 0; // 基础情况
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
执行过程示例（coins=[1,2,5], amount=11）：
| 金额 i | dp[i] 计算过程 | dp[i] 值 |
|---|---|---|
| 0 | 基础情况 | 0 |
| 1 | min(dp[0]+1) = 1 | 1 |
| 2 | min(dp[1]+1, dp[0]+1) = min(2,1) = 1 | 1 |
| 3 | min(dp[2]+1, dp[1]+1) = min(2,2) = 2 | 2 |
| 4 | min(dp[3]+1, dp[2]+1) = min(3,2) = 2 | 2 |
| 5 | min(dp[4]+1, dp[3]+1, dp[0]+1) = min(3,3,1) = 1 | 1 |
| 6 | min(dp[5]+1, dp[4]+1, dp[1]+1) = min(2,3,2) = 2 | 2 |
| 7 | min(dp[6]+1, dp[5]+1, dp[2]+1) = min(3,2,2) = 2 | 2 |
| 8 | min(dp[7]+1, dp[6]+1, dp[3]+1) = min(3,3,3) = 3 | 3 |
| 9 | min(dp[8]+1, dp[7]+1, dp[4]+1) = min(4,3,3) = 3 | 3 |
| 10 | min(dp[9]+1, dp[8]+1, dp[5]+1) = min(4,4,2) = 2 | 2 |
| 11 | min(dp[10]+1, dp[9]+1, dp[6]+1) = min(3,4,3) = 3 | 3 |
关键点分析：
amount + 1 表示不可达，因为最多需要 amount 个硬币（全部用面额 1）amount + 1，说明无法组成记忆化搜索的优势：
动态规划的优势：
性能对比：
BFS 解法将问题转化为最短路径问题：
// BFS 的关键逻辑
while (!queue.isEmpty()) {
level++;
int size = queue.size();
for (int i = 0; i < size; i++) {
int current = queue.poll();
for (int coin : coins) {
int next = current + coin;
if (next == amount) {
return level; // 找到最短路径
}
if (next < amount && !visited.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
}
}
BFS 的优势：
BFS 的劣势：
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 记忆化搜索 | O(amount × n) | O(amount) | 理解递归思维 |
| 动态规划 | O(amount × n) | O(amount) | 生产环境 |
| BFS | O(amount × n) | O(amount) | 需要早期终止 |
| 贪心（错误） | O(n log n) | O(1) | 仅适用于规范硬币系统 |
其中 n = coins.length
结论：动态规划方法在通用性和稳定性上表现最佳，是实际开发中的首选方案。BFS 在可以早期终止的情况下表现优秀，但最坏情况下不如动态规划稳定。
答：这是一个很好的扩展问题！动态规划方法可以轻松重构路径：
测试示例：
关键思想：在 DP 过程中记录每个状态使用的硬币通过回溯重构具体方案时间复杂度仍为 O(amount × n)，空间复杂度 O(amount)
答：这是一个常见的变种！假设每种硬币有使用次数限制。
问题分析：输入：硬币面额数组、对应数量限制、目标金额约束：每种硬币最多使用指定次数目标：求最少硬币数量
解决方案：多重背包问题
代码实现（二进制优化）：
复杂度分析：时间复杂度：O(amount × log(total_limit)) 空间复杂度：O(amount)
实际应用：库存管理（有限数量的商品）资源调度（有限的资源配额）游戏道具使用（有限次数的技能）
答：这是一个更复杂的扩展！需要找到所有最优解。
解决方案：在动态规划基础上，记录所有可能的前驱
代码实现：
复杂度分析：时间复杂度：O(amount × n × C)，其中 C 是最优组合的数量 空间复杂度：O(amount × C)注意：最优组合数量可能指数级增长
优化建议：如果只需要组合数量，不需要存储具体组合 可以限制返回的组合数量（如最多返回 10 个）
实际应用：投资组合多样化 菜单营养搭配方案 密码学中的多重分解
答：对于超大 amount，需要考虑不同的策略：
动态规划的局限性：空间复杂度 O(amount)，对于 amount=10^6 需要 4MB 内存 对于 amount=10^9，需要 4GB 内存，不可行
替代方案：
1. 数学优化（针对特定硬币系统）：
2. 分治策略：将大金额分解为多个小金额 利用硬币面额的最大公约数
3. 近似算法：
4. 流式处理：对于在线查询，可以预计算小金额的结果 大金额使用数学方法或近似算法
实际建议：对于 amount ≤ 10^4，动态规划是最佳选择 对于 amount > 10^4，需要根据硬币系统特性选择算法 在生产环境中，通常会有金额上限约束
答：这是一个很好的边界条件问题！
问题分析：面额为 0：使用 0 面额硬币没有意义，应该过滤掉面额为负数：在实际场景中不应该出现，需要验证输入
解决方案：
测试用例：
工程实践：输入验证：在生产代码中必不可少数据清洗：过滤无效数据，提高算法效率异常处理：提供清晰的错误信息
总结：在实际开发中，鲁棒性比算法本身更重要。良好的输入验证和错误处理能够避免很多潜在的问题。
public int coinChangePreprocessed(int[] coins, int amount) {
if (amount == 0) return 0;
// 预处理：排序、去重、过滤
Set<Integer> uniqueCoins = new TreeSet<>();
for (int coin : coins) {
if (coin > 0 && coin <= amount) {
uniqueCoins.add(coin);
}
}
if (uniqueCoins.isEmpty()) {
return -1;
}
// 转换为数组（已排序）
int[] processedCoins = uniqueCoins.stream().mapToInt(i -> i).toArray();
// 动态规划
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : processedCoins) {
if (coin > i) break; // 提前终止（因为已排序）
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
public int coinChangeEarlyTermination(int[] coins, int amount) {
if (amount == 0) return 0;
// 检查是否可能组成（最大公约数检查）
int gcd = coins[0];
for (int i = 1; i < coins.length; i++) {
gcd = gcd(gcd, coins[i]);
}
if (amount % gcd != 0) {
return -1; // 不可能组成
}
// 如果只有面额 1，直接返回
if (coins.length == 1 && coins[0] == 1) {
return amount;
}
// 标准动态规划
return coinChangeStandard(coins, amount);
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = b; b = a % b; a = temp;
}
return a;
}
public int coinChangeBidirectionalBFS(int[] coins, int amount) {
if (amount == 0) return 0;
Set<Integer> forward = new HashSet<>();
Set<Integer> backward = new HashSet<>();
Set<Integer> visited = new HashSet<>();
forward.add(0);
backward.add(amount);
visited.add(0);
visited.add(amount);
int steps = 0;
while (!forward.isEmpty() && !backward.isEmpty()) {
// 选择较小的集合进行扩展
if (forward.size() > backward.size()) {
Set<Integer> temp = forward; forward = backward; backward = temp;
}
Set<Integer> nextLevel = new HashSet<>();
steps++;
for (int current : forward) {
// 向前扩展
for (int coin : coins) {
int next = current + coin;
if (next > amount) continue;
if (backward.contains(next)) {
return steps;
}
if (!visited.contains(next)) {
visited.add(next);
nextLevel.add(next);
}
}
// 向后扩展（从目标向起点）
for (int coin : coins) {
int prev = current - coin;
if (prev < 0) continue;
if (backward.contains(prev)) {
return steps;
}
if (!visited.contains(prev)) {
visited.add(prev);
nextLevel.add(prev);
}
}
}
forward = nextLevel;
}
return -1;
}
public class CachedCoinChange {
private static final int MAX_CACHE_AMOUNT = 10000;
private static final Map<String, Integer> cache = new ConcurrentHashMap<>();
public int coinChange(int[] coins, int amount) {
if (amount > MAX_CACHE_AMOUNT) {
return coinChangeUncached(coins, amount);
}
String key = generateCacheKey(coins, amount);
return cache.computeIfAbsent(key, k -> coinChangeUncached(coins, amount));
}
private String generateCacheKey(int[] coins, int amount) {
return Arrays.toString(coins) + ":" + amount;
}
private int coinChangeUncached(int[] coins, int amount) {
// 标准动态规划实现
return coinChangeStandard(coins, amount);
}
}
public int[] coinChangeBatch(int[] coins, int[] amounts) {
return Arrays.stream(amounts).parallel().map(amount -> coinChange(coins, amount)).toArray();
}
答：这是一个非常重要的问题！让我详细解释贪心算法失败的原因：
贪心策略：总是选择不超过剩余金额的最大硬币面额
反例分析：输入：coins = [1, 3, 4], amount = 6贪心过程：6 - 4 = 2（选择 4）2 - 1 = 1（选择 1）1 - 1 = 0（选择 1）总计：3 枚硬币最优解：6 = 3 + 3，只需 2 枚硬币
根本原因：
1. 局部最优 ≠ 全局最优：贪心在每一步都做出局部最优选择（选择最大的硬币）但这种选择可能导致后续需要更多的小硬币在 6 的例子中，选择 4 看似最优，但实际上限制了后续的选择
2. 硬币系统的非规范性：在标准货币系统（1,5,10,25）中，贪心算法是有效的这是因为这些面额具有"规范性"（canonical property）[1,3,4] 这样的系统不具有规范性
3. 数学证明：可以证明存在无穷多个反例更一般地，当最优解需要多个相同的小面额硬币时，贪心容易失败
如何判断贪心是否适用：理论方法：验证硬币系统是否具有规范性（NP-hard）实践方法：寻找反例安全做法：当不确定时，使用动态规划
总结：贪心算法在这个问题中失败的根本原因是硬币系统不具有规范性，局部最优选择不能保证全局最优。这也是为什么我们需要使用动态规划来解决这个问题。
答：这是一个很好的对比问题！让我从多个维度分析两者的区别：
1. 思维方式：记忆化搜索：自顶向下，递归思维，符合人类直觉动态规划：自底向上，迭代思维，需要规划计算顺序
2. 实现复杂度：记忆化搜索：实现简单，直接在递归基础上加缓存动态规划：需要仔细设计状态转移和初始化
3. 性能特点：
4. 空间使用：记忆化搜索：需要额外的递归栈空间动态规划：只有 DP 数组空间
5. 适用场景：
选择记忆化搜索的情况：问题状态空间稀疏（很多状态不会被访问）递归关系复杂，难以确定计算顺序需要早期终止（某些分支可以提前返回）
选择动态规划的情况：问题状态空间密集（大部分状态都会被访问）需要重构具体方案（路径）对性能要求极高（避免递归开销）生产环境（代码更稳定，调试更容易）
零钱兑换中的选择：状态空间：密集（需要计算 0 到 amount 的所有状态）性能要求：高（避免递归开销）生产环境：需要稳定可靠的代码结论：动态规划是更好的选择
实际代码对比：
总结：虽然两种方法的时间复杂度相同，但在零钱兑换这类状态空间密集的问题中，动态规划通常是更好的选择，因为它避免了递归开销，代码更稳定，更适合生产环境。
答：这是一个很好的边界条件问题！让我分析大面额硬币的影响：
问题分析：
1. 内存溢出风险：如果 amount 很大（比如 10^9），会抛出 OutOfMemoryError 但在题目约束中，amount ≤ 10^4，所以这个问题在本题中不存在
2. 大面额硬币的处理：原因：面额大于 amount 的硬币在组成 amount 时永远不会被使用效果：减少内层循环次数，提高性能
3. 整数溢出问题：如果 amount = Integer.MAX_VALUE，amount + 1 会溢出解决方案：使用 Integer.MAX_VALUE 作为不可达标记
4. 改进的鲁棒实现：
5. 超大 amount 的处理策略：数学方法：对于规范硬币系统，使用贪心近似算法：接受次优解以换取性能分治策略：将大问题分解为小问题
工程实践建议：输入验证：始终验证输入参数的合理性防御性编程：处理各种边界情况性能监控：监控内存使用和执行时间
总结：虽然本题的约束条件保证了 amount 不会太大，但在实际开发中，我们必须考虑各种极端情况。良好的工程实践包括输入验证、边界处理和性能优化。
答：这是一个很有洞察力的问题！零钱兑换问题实际上是背包问题的一个经典特例。
背包问题的一般形式：0-1 背包：每个物品只能选择 0 次或 1 次完全背包：每个物品可以选择无限次多重背包：每个物品有选择次数限制
零钱兑换作为完全背包问题：
1. 问题映射：物品：不同面额的硬币物品价值：1（每个硬币的"代价"都是 1）物品重量：硬币面额背包容量：目标金额 amount优化目标：最小化总价值（即最少物品数量）
2. 状态转移对比：
3. 关键差异：目标函数：背包问题通常最大化价值，这里是最小化数量****物品价值：背包问题中物品价值可以不同，这里所有物品价值都是 1可行性：背包问题通常保证有解，这里可能无解（返回 -1）
4. 算法复杂度对比：标准完全背包：O(amount × n)零钱兑换：O(amount × n)复杂度相同，但目标函数不同
5. 更一般的推广：
6. 实际应用对比：背包问题：资源分配、投资组合、装箱问题零钱兑换：找零系统、货币兑换、资源优化
总结：零钱兑换问题是完全背包问题在特定目标函数下的实例。理解这种关系有助于我们将已知的背包问题算法应用到新的场景中，同时也提醒我们要注意特定问题的特殊性质（如可能无解的情况）。
答：这是一个很好的工程实践问题！让我从系统设计的角度分析：
需求分析：高并发：大量用户同时请求找零方案低延迟：响应时间要求严格（ - 大数据量：amount 范围可能很大高可用：系统需要容错和扩展
架构设计方案：
1. 分层架构：
2. 缓存策略：
方案 A：本地缓存（小 amount）
方案 B：分布式缓存（Redis）
3. 计算优化：
预计算表（固定硬币系统）：如果硬币系统固定（如标准货币系统），可以预计算所有结果查询时 O(1) 响应内存占用：40KB（10000 个整数）
动态计算（可变硬币系统）：使用优化的动态规划算法复杂度 O(amount × n)
4. 负载均衡：
5. 监控和告警：
6. 性能指标：QPS：单机可达 5,000+（缓存命中）P99 延迟： - 内存使用： - CPU 使用： 7. 故障处理：缓存穿透：对不存在的组合也缓存（空值缓存）缓存雪崩：设置随机过期时间服务降级：缓存和计算层都失败时，返回默认值或错误
8. 扩展性考虑：水平扩展：无状态服务，易于扩展垂直扩展：增加内存以支持更大的预计算表功能扩展：支持批量查询、异步查询等
总结：在高并发支付系统中处理零钱兑换查询，缓存是关键。通过合理的分层架构、缓存策略和监控体系，可以构建高性能、高可用的服务。这也体现了"简单算法 + 工程优化 = 生产级解决方案"的工程哲学。
实现：
// ATM 找零系统
public List<Denomination> calculateChange(int amount, Denomination[] availableDenominations) {
int[] coins = Arrays.stream(availableDenominations).mapToInt(Denomination::getValue).toArray();
int minCoins = coinChange(coins, amount);
if (minCoins == -1) {
throw new InsufficientFundsException("Cannot make exact change");
}
return reconstructChange(coins, amount);
}
实现：
// 优惠券组合优化
public int minimizeCouponUsage(int totalDiscount, int[] couponValues) {
return coinChange(couponValues, totalDiscount);
}
实现：
// 游戏货币兑换
public ExchangePlan optimizeCurrencyExchange(int targetAmount, int[] denominations) {
int minCoins = coinChange(denominations, targetAmount);
List<Integer> combination = getCoinCombination(denominations, targetAmount);
return new ExchangePlan(minCoins, combination);
}
实现：
// 云服务器资源配置
public ServerConfiguration optimizeResourceAllocation(int requiredCores) {
int[] coreOptions = {1, 2, 4, 8, 16, 32};
int minServers = coinChange(coreOptions, requiredCores);
if (minServers == -1) {
// 需要组合不同规格的服务器
return createMixedConfiguration(requiredCores);
}
return createOptimalConfiguration(coreOptions, requiredCores);
}
实现：
// 数据库分片优化
public ShardPlan optimizeSharding(long totalDataSize, long[] shardSizes) {
// 转换为整数问题（以 GB 为单位）
int amount = (int)(totalDataSize / GB);
int[] coins = Arrays.stream(shardSizes).mapToInt(size -> (int)(size / GB)).toArray();
int minShards = coinChange(coins, amount);
return new ShardPlan(minShards, getCoinCombination(coins, amount));
}
实现：
// 物流包装优化
public PackagingPlan optimizePackaging(double totalWeight, double[] boxWeights) {
// 转换为整数（以克为单位）
int amount = (int)(totalWeight * 1000);
int[] coins = Arrays.stream(boxWeights).mapToInt(weight -> (int)(weight * 1000)).toArray();
int minBoxes = coinChange(coins, amount);
return new PackagingPlan(minBoxes, getCoinCombination(coins, amount));
}
💡 核心价值：零钱兑换问题不仅仅是一个算法练习，它代表了一类重要的资源优化问题。在实际开发中，只要遇到"用最少的固定规格单元组成目标值"的需求，就可以考虑使用相关的算法思想。
| 题号 | 题目 | 难度 | 关联点 |
|---|---|---|---|
| 322 | 零钱兑换 | 中等 | 本题 |
| 518 | 零钱兑换 II | 中等 | 完全背包计数 |
| 279 | 完全平方数 | 中等 | 完全背包特例 |
| 377 | 组合总和 IV | 中等 | 排列 vs 组合 |
| 416 | 分割等和子集 | 中等 | 0-1 背包 |
| 139 | 单词拆分 | 中等 | 字符串 DP |
🔔 重点：零钱兑换问题是背包问题系列中的重要一环。通过这一系列题目，你可以逐步掌握从简单 0-1 背包到复杂约束 DP 的各种技巧，为解决更困难的算法问题打下坚实基础。
动态规划基础
背包问题
零钱兑换
完全背包变种
复杂优化问题
// 零钱兑换动态规划模板
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
// 通用思想：完全背包问题的最小化版本
🌟 最后寄语：零钱兑换这道题完美展示了动态规划在实际问题中的强大威力。它教会我们不仅要掌握算法框架，更要理解问题的本质和约束条件。在实际开发中，这种"算法思维 + 工程实践"的组合往往能带来意想不到的效果。记住，优秀的程序员不仅要会写代码，更要懂算法、懂系统、懂业务。继续探索，算法的世界远比你想象的更加精彩！
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online