322、零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
- 说明: 你可以认为每种硬币的数量是无限的。
题解
1、回溯法——递归实现
$$
\min_{x} \sum_{i=0}^{n - 1} x_i \ \text{subject to} \sum_{i=0}^{n - 1} x_i*c_i = S
$$
// java
class Solution {
public int coinChange(int[] coins, int amount) {
// 构造回溯函数求解，参数：处理到硬币的下标，硬币列表，目标值
return coinChange(0,coins,amount);
}
private int coinChange(int idxCoin, int[] coins, int amount) {
// 外围，边界片判断
// 求解完成
if (amount == 0) {
return 0;
}
// 求解未完成, 没有遍历完全部硬币 且 目标值 ≥ 0
if(idxCoin < coins.length && amount > 0) {
int maxVal = amount/coins[idxCoin];
int minCost = Integer.MAX_VALUE;
// 对每一枚硬币的面值，进行枚举遍历
for (int i = 0;i <= maxVal;i++) {
// 递归求解，深度优先搜索
int res = coinChange(idxCoin+1,coins,amount- i * coins[idxCoin]);
// 存在有效解，更新最小花费
if (res != -1) {
minCost = Math.min(minCost,res + i);
}
}
// 返回最优结果
return (minCost == Integer.MAX_VALUE)? -1 : minCost;
}
// 求解结束
return -1;
}
}
2、动态规划
- 自上而下
- 从目标值出发求解，知道目标值变为0
- 代码：依然用回溯法实现
// java
class Solution {
public int coinChange(int[] coins, int amount) {
// 异常处理
if (amount < 1) return 0;
// 调用回溯函数，硬币列表，硬币总数，记忆化数组（减少不必要的计算）
return coinChange(coins,amount,new int[amount]);
}
private int coinChange(int[] coins,int rem, int[] count){
// 临界处理
if (rem < 0) return -1;
if (rem == 0) return 0;
// 存在已经求出来的解，直接使用
if (count[rem - 1] != 0) {
return count[rem - 1];
}
// 记录最小值
int min = Integer.MAX_VALUE;
// 求当前rem的解
for (int coin : coins) {
// 递归，更新剩余的总值
int res = coinChange(coins,rem - coin,count);
// 条件更新
if (res != -1 && res < min) {
min = 1 + res;
}
}
// 将结果记录下来
count[rem - 1] = (min == Integer.MAX_VALUE)? -1 : min;
// 返回结果
return count[rem - 1];
}
}
- 自下而上——真正的动态规划
- 从0出发，直到到达目标值
- $F(i) = \min_{j=0…n-1}F(i - c_i) + 1$
- 代码
// java
class Solution {
public int coinChange(int[] coins, int amount) {
// dp数组初值
int max = amount + 1;
// dp状态数组
int[] dp = new int[amount];
// 填充数组
Arrays.fill(dp,max);
dp[0] = 0;
// 遍历状态数组
for (int i = 1;i <= amount;i++) {
// 遍历硬币数组
for (int j = 0; j < coins.length;j++) {
// 处理有效硬币，更新最小值
if (i >= coins[j]) {
dp[i] = Math.min(dp[i],dp[i - coins[j]] + 1);
}
}
}
// 返回结果
return dp[amount] > amount ? -1 : dp[amount];
}
}
3、排序+深度优先搜索
class Solution {
private int min = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
// 排序
Arrays.sort(coins); // asc
// 递归
dfs(coins, coins.length - 1, amount, 0);
return min == Integer.MAX_VALUE ? -1 : min;
}
private void dfs(int[] coins, int ci, int rest, int cnt) {
if (ci < 0) return;
// 从大到小枚举可能的每一枚硬币值
for (int i = rest / coins[ci]; i >= 0; i--) {
// 获取剩下的待兑换的金额 以及 当前兑换的硬币数量
int currRest = rest - i * coins[ci], currCnt = cnt + i;
// 零钱没有兑换完 且 当前兑换可能是最小数量兑换
if (currRest > 0 && currCnt + 1 < min) dfs(coins, ci - 1, currRest, currCnt);
else {
// 更新最少的硬币数
if (currRest == 0 && currCnt < min) min = currCnt;
// 否则一定无解
break;
}
}
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
