使用 oh-my-zsh

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