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.
动态规划典型问题, 想一想递推关系是什么. 假设 dp[i]代表 i 这么多钱所需要的硬币数量, 那么对于每一个不同面值的硬币 coins[j]来说, dp[i] = dp[i - coins[j]] + 1. 只要在遍历 coins 面值的时候选择需要数量最小的就好, 即 min(dp[i], dp[i - coins[j]] + 1). 通用情况想完了就要想初始情况. dp[0]显然是 0, 不需要硬币组成 0 元. 而既然在递推中要用到 min, 那么把所有值初始为 amount + 1 的话即可, 因为硬币都是正数, 不可能会存在需要比 amount 还多硬币的情况. 如果最后得到的结果比 amount 大 (其实题里并没有说 amount 不会是最大正数, 否则这样取值就会 overflow 产生错误, test case 里面并没有这种情况), 证明没有办法组成面值, 需要返回 - 1. 需要注意的是因为 i-coins[j] 作为数组下标出现, 显然 conis[j]不能比 i 大.
- Java
- class Solution {
- public int coinChange(int[] coins, int amount) {
- if (coins == null || coins.length == 0 || amount <= 0) return 0;
- int[] dp = new int[amount + 1];
- Arrays.fill(dp, amount + 1);
- dp[0] = 0;
- for (int j = 0; j <coins.length; j++)
- for (int i = coins[j]; i <= amount; i++)
- dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
- return dp[amount]> amount ? -1 : dp[amount];
- }
- }
来源: http://www.bubuko.com/infodetail-2666296.html