​LeetCode刷题实战322：零钱兑换

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 零钱兑换，我们先来看题面：

https://leetcode-cn.com/problems/coin-change/

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

给定不同面额的硬币 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

示例 4：

输入：coins = [1], amount = 1
输出：1

示例 5：

输入：coins = [1], amount = 2
输出：2

解题

https://blog.csdn.net/qq_23128065/article/details/104729144

背包问题的思路，首先一个ans数组，存储当前index的钱应该用几个coins，主要思路就是，要么是当前index中存储的需要的硬币个数，要么是当前index值的amount需要当前ans[index]中存储的硬币个数，要么是ans[index-coins[i]]+1,这个是如果加上当前面值coins[i]的硬币时，那么当前amount就是index-coins[i]，所以查看ans[index-coins[i]]中存储的硬币个数，然后加上当前这一枚硬币，就是amount为index时所需的硬币个数，取这两种可能中的最小值就是所需最少硬币个数。

递推方程如下：

ans[i] = Math.min(ans[i],ans[i-coins[j]]+1);

计算过程如下图所示：

最后的ans[amount]中存储的就是兑换amount所需的硬币个数。

代码如下：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] ans = new int[amount+1];
        Arrays.fill(ans,amount+1);
        ans[0] = 0;
        for(int j = 0;j<coins.length;j++){
            for(int i=1;i<ans.length;i++){
                if(i>=coins[j]){
                    ans[i] = Math.min(ans[i],ans[i-coins[j]]+1);
                }
            }
        }
        return ans[amount]>amount?-1:ans[amount];
    }
}

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。