LeetCode.322.Coin Change 零钱兑换

题目描述

322 Coin Change
https://leetcode-cn.com/problems/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.

Example 1:

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.

---

相似题目

LeetCode.322.Coin Change 零钱兑换
LeetCode.程序员面试金典.0811.Coin 硬币

---

解题过程

设 f(i) 是兑换金额 i 需要的最小零钱个数，硬币集合为 {c1, c2, …, cj} ，则有递推公式：
$
f(i) = \min_{j = 1…n} f(i - c_j) + 1
$

时间复杂度 O(mn)，其中m是金额，n是硬币个数，空间复杂度 O(m)，其中m是金额

private static class SolutionV2020 {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            int min = -1;
            for (int coin : coins) {
                if (i == coin) {
                    // 当前硬币就是要找的金额
                    min = 1;
                    break;
                } else if (i > coin) {
                    if (dp[i - coin] == -1) {
                        // 找不开
                        continue;
                    }
                    min = (-1 == min ? dp[i - coin] + 1 : Math.min(min, dp[i - coin] + 1));
                }
            }
            dp[i] = min;
        }
        return dp[amount];
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_322_CoinChange.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_322_CoinChange.java

---