更多算法题的题解见：算法刷题题解汇总（持续更新中）
一、问题背景
小C有多种不同面值的硬币，每种硬币的数量是无限的。他希望知道，如何使用最少数量的硬币，凑出给定的总金额N。小C对硬币的组合方式很感兴趣，但他更希望在满足总金额的同时，使用的硬币数量尽可能少。
例如：小C有三种硬币，面值分别为 1, 2, 5。他需要凑出总金额为 18。一种最优的方案是使用三个 5 面值的硬币，一个 2 面值的硬币和一个 1 面值的硬币，总共五个硬币。
二、问题分析
- 小C有多种不同面值的硬币，每种硬币的数量是无限的。
- 他需要凑出总金额为N的硬币组合。
- 我们的目标是使用最少数量的硬币，满足总金额的要求。
三、解题思路
- 初始化动态规划数组：创建一个动态规划数组dp，其中dp[i]表示凑出金额i时，最少需要的硬币数。
- 初始化coinUsed数组：创建一个数组coinUsed，用于记录每个金额是通过使用哪个硬币得到的。
- 遍历硬币数组：从大到小遍历硬币数组，优先考虑大面值硬币。
- 更新dp数组：对于每个硬币，如果它小于或等于当前金额i，则尝试使用这个硬币，并更新dp数组和coinUsed数组。
- 回溯求解：通过coinUsed数组回溯，找到硬币组合。
参考代码如下：
public class Main {
public static List<Integer> solution(int[] coins, int total) {
int[] dp = new int[total + 1];
int[] coinUsed = new int[total + 1];
for (int i = 1; i <= total; i++) {
dp[i] = total + 1;
}
Arrays.sort(coins);
for (int i = 1; i <= total; i++) {
for (int j = coins.length - 1; j >= 0; j--) {
int coin = coins[j];
if (coin <= i) {
if (dp[i - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
coinUsed[i] = coin;
}
}
}
}
// 无法组成该金额
if (dp[total] == total + 1) {
return new ArrayList<>();
}
// 回溯找到硬币组合
List<Integer> result = new ArrayList<>();
int remaining = total;
while (remaining > 0) {
int coin = coinUsed[remaining];
result.add(coin);
remaining -= coin;
}
return result;
}
}
关键步骤解析
- 动态规划数组dp：dp数组用于记录每个金额最少需要的硬币数。初始化时，除了dp[0]外，其它都设置为最大值，因为0不需要任何硬币。
- coinUsed数组：coinUsed数组用于记录每个金额是通过使用哪个硬币得到的。通过这个数组，我们可以回溯出硬币组合。
- 硬币数组排序：在遍历硬币数组时，我们首先对硬币数组进行从大到小的排序，这样我们可以优先考虑大面值的硬币，从而减少硬币的数量。
- 更新dp数组：在遍历硬币数组时，我们尝试使用每个硬币，并更新dp数组和coinUsed数组。如果使用当前硬币后，所需硬币数更少，则更新dp数组和coinUsed数组。
- 回溯求解：通过coinUsed数组回溯，找到硬币组合。从总金额开始，逐个减去硬币面值，直到金额为0，将硬币面值添加到结果列表中。
算法优势
- 动态规划：通过动态规划，我们可以找到最优解，使得硬币的数量尽可能少。
- 排序：对硬币数组进行排序，优先考虑大面值硬币，可以减少硬币的数量。
- 回溯：通过回溯，我们可以找到硬币组合。
复杂度分析
时间复杂度分析：
- 初始化动态规划数组和硬币使用数组的时间复杂度为 O(total + 1)，因为需要创建一个长度为 total + 1 的数组。
- 对硬币数组进行排序的时间复杂度为 O(coins.length * log(coins.length))，其中 coins.length 是硬币数组的长度。
- 遍历硬币数组和总金额的时间复杂度为 O(total * coins.length)，因为对于每个金额 i，我们需要遍历所有硬币。
- 更新动态规划数组和硬币使用数组的时间复杂度为 O(1)，因为每个操作的时间复杂度为常数。
- 通过硬币使用数组回溯找到硬币组合的时间复杂度为 O(total)，因为需要遍历总金额。
因此，整个算法的时间复杂度：
O
(
t
o
t
a
l
∗
c
o
i
n
s
.
l
e
n
g
t
h
+
c
o
i
n
s
.
l
e
n
g
t
h
∗
l
o
g
(
c
o
i
n
s
.
l
e
n
g
t
h
)
)
O(total * coins.length + coins.length * log(coins.length))
O(total∗coins.length+coins.length∗log(coins.length)) 通常情况下，如果total远大于coins.length，则可以简化为O(total * coins.length)
空间复杂度分析：
- 动态规划数组和硬币使用数组的空间复杂度为
O(total + 1)，因为需要创建一个长度为tal + 1数组。 - 结果列表的空间复杂度为
O(total)，因为需要存储每个金额是通过使用哪个硬币得到的。 - 其他变量的空间复杂度为
O(1)。
因此，空间复杂度：O(total)，呈线性关系