[Leetcode] 322. Coin Change | 零钱兑换

yPhantom 2020年02月05日 29次浏览

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.

这是一道完全背包问题,面对完全背包问题,不要去想0/1背包的二维转一维,我们可以直接用一维的方式来理解。其核心函数就是:

dp[amount] = min(dp[amount], dp[amount - coins[i]] + 1)

不论是基本的0/1背包问题,还是完全背包问题,它们转成一维的时候,都是以“和”作为dp数组的下标。基本的0/1背包,内存循环为逆序。完全背包为顺序。

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