企业官网建设流程全解析

题目描述：

给你一个整数数组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

解题思路：

方法一：动态规划（完全背包）

核心思路：

状态定义：

dp[i]= 凑出金额i所需的最少硬币数。

状态转移：

对于每个金额i，枚举所有硬币coin：

• 如果i >= coin，说明可以用这枚硬币

• dp[i] = min(dp[i], dp[i - coin] + 1)

初始化：

• dp[0] = 0（凑出 0 需要 0 枚硬币）

• 其他初始化为amount + 1（表示不可达，因为最多用amount枚 1 元硬币）

具体过程示例：

coins = [1, 2, 5], amount = 11

结果：3✅

代码实现：

写法1：外层金额，内层硬币

class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, amount + 1); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (i >= coin) { dp[i] = min(dp[i], dp[i - coin] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } };

写法2：外层硬币，内层金额（标准完全背包）

class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, amount + 1); dp[0] = 0; for (int coin : coins) { for (int i = coin; i <= amount; i++) { dp[i] = min(dp[i], dp[i - coin] + 1); } } return dp[amount] > amount ? -1 : dp[amount]; } };

两种写法都可以，因为求的是最少数量，顺序不影响结果。

复杂度分析：

设n是硬币种类数，amount是总金额。

关键细节：

1. 为什么初始化为amount + 1？

• 最多用amount枚 1 元硬币凑出amount

• 所以amount + 1可以表示"不可达"

• 最后判断dp[amount] > amount就知道是否凑得出

2. 为什么dp[0] = 0？

凑出金额 0 需要 0 枚硬币。

3. 为什么返回-1？

如果dp[amount]仍然是初始值amount + 1，说明凑不出。

4. 和「完全平方数」的区别

本质完全一样，都是完全背包求最少数量。

方法二：BFS（层序遍历）

思路：

把金额看作节点，每次减去一个硬币面额，看最少几步到达 0。

代码实现：

class Solution { public: int coinChange(vector<int>& coins, int amount) { if (amount == 0) return 0; queue<int> q; q.push(amount); vector<bool> visited(amount + 1, false); visited[amount] = true; int level = 0; while (!q.empty()) { int size = q.size(); level++; for (int i = 0; i < size; i++) { int curr = q.front(); q.pop(); for (int coin : coins) { int next = curr - coin; if (next == 0) return level; if (next > 0 && !visited[next]) { visited[next] = true; q.push(next); } } } } return -1; } };

复杂度：时间 O(amount × n)，空间 O(amount)

方法三：记忆化搜索

代码实现：

class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> memo(amount + 1, -2); // -2 表示未计算 return dfs(coins, amount, memo); } private: int dfs(vector<int>& coins, int amount, vector<int>& memo) { if (amount == 0) return 0; if (amount < 0) return -1; if (memo[amount] != -2) return memo[amount]; int minCoins = INT_MAX; for (int coin : coins) { int sub = dfs(coins, amount - coin, memo); if (sub >= 0) { minCoins = min(minCoins, sub + 1); } } memo[amount] = (minCoins == INT_MAX) ? -1 : minCoins; return memo[amount]; } };

复杂度：时间 O(amount × n)，空间 O(amount)

三种方法对比：

总结：