Haiyang Yu's Blog
0%

Leetcode 322 Coin Change

发表于 更新于 分类于 Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

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.

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

Example 1:

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

Example 2:

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

Example 3:

1
2
Input: coins = [1], amount = 0
Output: 0

Example 4:

1
2
Input: coins = [1], amount = 1
Output: 1

Example 5:

1
2
Input: coins = [1], amount = 2
Output: 2

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

动态规划

回溯是肯定不行的, 太慢了.如果碰到这样的用例, coins = [1,100], amount = 10000就惨了.

首先创建一个dp数组int[] dp = new int[amount + 1];

dp[i]表示组成amount 为 i的所用最少硬币数. 初始时数组全部为-1.

首先, 边界条件是dp[0] = 0

对于dp[i], 想要找到组成i所需要的最小硬币数, 假设最后一个组成i的硬币为j, 那么通过j组成i的硬币数就为dp[i - j] + 1. 前提是i - j > 0并且dp[i - j] != -1.

对于在coins中的所有满足上述条件的j, 选取一个使得dp[i - j] + 1最小的j, 即为dp[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for(int i = 0; i < dp.length; ++i)
            dp[i] = -1;
        dp[0] = 0;
        for(int i = 1; i < dp.length; ++i)
        {
            int minCoins = Integer.MAX_VALUE;
            for(int j : coins)
            {
                int tmp = i - j;
                if(tmp < 0 || dp[tmp] == -1)
                    continue;
                else
                {
                    int currCoins = dp[tmp] + 1;
                    minCoins = Math.min(minCoins, currCoins);
                }
            }
            dp[i] = minCoins == Integer.MAX_VALUE ? -1 : minCoins;
        }
        return dp[amount];
    }
}