You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return 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:
Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3 Output: -1
Example 3:
Input: coins = [1], amount = 0 Output: 0
Constraints:
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins =[1, 2, 5], amount =11输出：3解释：11 = 5 + 5 + 1
示例 2：
输入：coins =[2], amount =3输出：-1
示例 3：
输入：coins = [1], amount = 0 输出：0
提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
| Language | Runtime | Memory | Submission Time |
|---|---|---|---|
| typescript | 92 ms | 46.9 MB | 2023/04/04 21:55 |
function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 0; i <= amount; i++) {
for (let j = 0; j < coins.length; j++) {
if (i >= coins[j]) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
};似乎是完全背包问题的一种变体。
设 dp[i] 是金额为 i时，所有的硬币凑成这个i所用的个数最小值。写出状态转移就比较简单了：
function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 0; i <= amount; i++) {
for (let j = 0; j < coins.length; j++) {
if (i >= coins[j]) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
};要注意dp 要初始化为全是Infinity。最后如果 dp 是infinity的话，实际上是没找到所有硬币使得满足这个 amout，所以需要返回 -1。