转载

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.

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.

难度：medium

题目：给定不同面值的硬币和一总金额。写一个函数来计算你需要的最少的硬币数量来构成这个总金额。如果这笔钱不能用硬币的任何组合来构成，则返回-1。

思路：DP

total[i]表示这个金额最少需要多少硬币组成。

total[amount] = Math.min(total[amount - coins[i]] + 1) (total[amount - coins[i]] > 0)

(total[amount - coins[i]] = 0) 意味着不可达。

Runtime: 13 ms, faster than 97.29% of Java online submissions for Coin Change.

Memory Usage: 38 MB, less than 42.39% of Java online submissions for Coin Change.

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

原文 https://segmentfault.com/a/1190000018386573

正文到此结束