【LeetCode】322. Coin Change 硬币找零

本文主要是介绍【LeetCode】322. Coin Change 硬币找零，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

• You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.

Example1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:
Input: coins = [2], amount = 3
Output: -1

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

---

本题含义：给定一些面值的硬币，假设每种面值的硬币数量无限，在给定一个钱数，问最少用几个硬币来找零，如果给定的硬币不能凑出给定的钱数，则返回-1。
这道题其实题后面给出了较为详细的解答，本文主要是为了加深印象，巩固基础方便复习，对其中的内容进行摘录。详情请见Leetcode 322. Coin Change. 网站中提出了三种解决方案。第一种是用Brute force，本文省略，主要记录下是用动态规划进行求解的方法。
这道题属于完全背包问题。

思路一： Dynamic programming - Top down

$F(amount)$ 表示是用$coins[0],coins[1],\cdot \cdot \cdot ,coins[n-1]$构成的最少数量
动态规划思想的核心是寻找最优子问题，因此本题的最主要的目标就是寻找该问题的最优子问题。
假设$F(S)$表示由硬币数组$coins$构成需要的最少数量的硬币数，并且假设最后一个构成$S$的硬币是$C$，因此$$F(S)=F(S-C)+1$$但实际上我们不确定最后构成$S$的硬币是 c o i n s = { c 0 , c 1 , ⋅ ⋅ ⋅ , c n − 1 } coins = \{c_0, c_1,\cdot\cdot\cdot,c_{n-1}\} coins={c0​,c1​,⋅⋅⋅,cn−1​}中的哪一个，因此我们进行遍历计算$F(S-c_i)$，选择其中$F(S-c_i)$最小的那个$c_i$
$$F(S)=\{\begin{array}{ll}0,& \text{if S=0 }\\ mi{n}_{i=0,\cdot \cdot \cdot ,n-1}F(S-c_i)+1,& \text{if S−ci≥0 }\\ -1& \text{other }\end{array}$$

算法
该算法主要思想是自顶下下的解决方式。主要使用回溯以及在回归树中进行减枝。为了防止重复计算，使用一个数组存储子问题的解决方案。以下是代码

public class Solution {public int coinChange_TopDown(int[] coins, int amount) {if (amount <= 0)return 0;return coinChange(coins, amount, new int[amount]);}/*** @param count: 存储子问题的解* */public int coinChange(int[] coins, int remain, int[] count) {if (remain < 0)return -1;if (remain == 0)return 0;if (count[remain - 1] != 0)return count[remain - 1];int min = Integer.MAX_VALUE;for (int coin: coins) {int res = coinChange(coins, remain - coin, count);if (res >= 0 && res < min)min = res + 1;}count[remain - 1] = (min == Integer.MAX_VALUE) ? -1 : min;return count[remain - 1];}
}

复杂度分析：
时间复杂度为：$O(S\ast n)$，其中$S$是amount值本身，$n$是数组$coins$的大小
空间复杂度为：$O(S)$，主要用于记录子问题的解

---

思路二： Dynamic programming - Bottom up

第二种主要是使用迭代的方法进行计算，在计算$F(amount)$之前，已经计算好了构成$0,1,\cdot \cdot \cdot ,n-1$的解。因此计算$$F(amount)=mi{n}_{i=0,\cdot \cdot \cdot ,n-1}F(amount-coins[i])+1$$

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

复杂度分析：
时间复杂度为：$O(S\ast n)$，其中$S$是amount值本身，$n$是数组$coins$的大小
空间复杂度为：$O(S)$，主要用于记录子问题的解

这篇关于【LeetCode】322. Coin Change 硬币找零的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---