当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.322.Coin Change 零钱兑换

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


上一篇 LeetCode.1013.Partition Array Into Three Parts With Equal Sum 将数组分成和相等的三个部分

下一篇 LeetCode.剑指offer.059.最大队列

阅读
评论
302
阅读预计1分钟
创建日期 2020-03-08
修改日期 2020-03-08
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论