Leetcode 322 零钱兑换
给你一个整数数组 coins
,表示不同面额的硬币;以及一个整数 amount
,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1
。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins = [1, 2, 5], amount = 11示例 2:
输出:3
解释:11 = 5 + 5 + 1
输入:coins = [2], amount = 3示例 3:
输出:-1
输入:coins = [1], amount = 0示例 4:
输出:0
输入:coins = [1], amount = 1示例 5:
输出:1
输入:coins = [1], amount = 2解题思路 这道题有些人可能会想到贪心法,优先用面值大的硬币去凑,但是贪心无法获得最优解。例如下面这个例子:
输出:2
int[] coins = {1, 2, 5, 7, 10};
int amount = 14;
假如用贪心法,那么首先肯定是用面值为
10
的硬币,然后还需两个面值为 2
的硬币,总共需要 3
个硬币。但事实上,只需要两个面值为 7
的硬币就能凑出 14
的金额。因此这道题需要用动态规划的思想。【Leetcode 322 零钱兑换】从下面这个表格可以看出动态规划的思路,对于需要拼凑的金额
i
,遍历硬币面值,找到面值比金额低的硬币 coins[j]
,然后再去看 dp
数组中 dp[i - coins[j]]
是否有最优解,把所有可能的情况都列出,找最小的即可。整个过程从 1
开始不断迭代,一直迭代到需要的金额即可。金额 | 可以凑出的情况 | 最优解 |
---|---|---|
0 | - | 0 |
1 | 1 | 1(使用一个面值为 1 的硬币) |
2 | 2 | 1(使用一个面值为 2 的硬币) |
3 | 1 + dp[2], 2 + dp[1] | 2(都是最优解) |
4 | 1 + dp[3], 2 + dp[2] | 2(2 + dp[2]) |
5 | 5 | 1(使用一个面值为 5 的硬币) |
6 | 1 + dp[5], 2 + dp[4], 5 + dp[1] | 2(1 + dp[5] 或者 5 + dp[1]) |
7 | 7 | 1(使用一个面值为 7 的硬币) |
8 | 1 + dp[7], 2 + dp[6], 5 + dp[3], 7 + dp[1] | 2(1 + dp[7] 或者 7 + dp[1]) |
9 | 1 + dp[8], 2 + dp[7], 5 + dp[4], 7 + dp[2] | 2(2 + dp[7] 或者 7 + dp[2]) |
10 | 10 | 1(使用一个面值为 10 的硬币) |
11 | 1 + dp[10], 2 + dp[9], 5 + dp[6], 7 + dp[4], 10 + dp[1] | 2(1 + dp[10] 或者 10 + dp[1]) |
12 | 1 + dp[11], 2 + dp[10], 5 + dp[7], 7 + dp[5], 10 + dp[2] | 2(2 + dp[10] 或者 5 + dp[7] 或者 7 + dp[5] 或者 10 + dp[2]) |
13 | 1 + dp[12], 2 + dp[11], 5 + dp[8], 7 + dp[6], 10 + dp[3] | 3(都是最优解) |
14 | 1 + dp[13], 2 + dp[12], 5 + dp[9], 7 + dp[7], 10 + dp[4] | 2(7 + dp[7]) |
import java.util.Arrays;
public class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// 初始化 dp 数组,大小为 amount + 1
Arrays.fill(dp, -1);
// 全部元素初始化为 -1
dp[0] = 0;
// 金额 0 的最优解 dp[0]=0// 依次计算 1 至 amount 的最优解
for (int i = 1;
i <= amount;
i++) {
// 对于每个金额 i ,遍历面值 coins 数组
for (int j = 0;
j < coins.length;
j++) {
// 需要拼凑的面额 i 比当前面值 coins[j] 大,且金额 i - coins[j] 有最优解
if (coins[j] <= i && dp[i - coins[j]] != -1) {
// 如果当前金额还未计算或者 dp[i] 比当前计算的值大
if (dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1) {
dp[i] = dp[i - coins[j]] + 1;
// 更新 dp[i]
}
}
}
}
return dp[amount];
// 返回金额 amount 的最优解 dp[amount]
}
}
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)
- LeetCode(03)Longest|LeetCode(03)Longest Substring Without Repeating Characters
- 20180322【w4复盘日志】
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路