class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
}
};
322. 零钱兑换
给你一个整数数组 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相似题目
原站题解
golang 解法, 执行用时: 9 ms, 内存消耗: 6.2 MB, 提交时间: 2024-03-24 10:01:36
func coinChange(coins []int, amount int) int {
f := make([]int, amount+1)
for i := range f {
f[i] = math.MaxInt / 2 // 除 2 是防止下面 + 1 溢出
}
f[0] = 0
for _, x := range coins {
for c := x; c <= amount; c++ {
f[c] = min(f[c], f[c-x]+1)
}
}
ans := f[amount]
if ans < math.MaxInt/2 {
return ans
}
return -1
}
golang 解法, 执行用时: 20 ms, 内存消耗: 6.8 MB, 提交时间: 2024-03-24 10:01:06
func coinChange(coins []int, amount int) int {
n := len(coins)
f := make([][]int, 2)
for i := range f {
f[i] = make([]int, amount+1)
}
for j := range f[0] {
f[0][j] = math.MaxInt / 2 // 除 2 是防止下面 + 1 溢出
}
f[0][0] = 0
for i, x := range coins {
for c := 0; c <= amount; c++ {
if c < x {
f[(i+1)%2][c] = f[i%2][c]
} else {
f[(i+1)%2][c] = min(f[i%2][c], f[(i+1)%2][c-coins[i]]+1)
}
}
}
ans := f[n%2][amount]
if ans < math.MaxInt/2 {
return ans
}
return -1
}
golang 解法, 执行用时: 16 ms, 内存消耗: 6.8 MB, 提交时间: 2024-03-24 10:00:44
func coinChange(coins []int, amount int) int {
n := len(coins)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, amount+1)
}
for j := range f[0] {
f[0][j] = math.MaxInt / 2 // 除 2 是防止下面 + 1 溢出
}
f[0][0] = 0
for i, x := range coins {
for c := 0; c <= amount; c++ {
if c < x {
f[i+1][c] = f[i][c]
} else {
f[i+1][c] = min(f[i][c], f[i+1][c-x]+1)
}
}
}
ans := f[n][amount]
if ans < math.MaxInt/2 {
return ans
}
return -1
}
golang 解法, 执行用时: 49 ms, 内存消耗: 8.5 MB, 提交时间: 2024-03-24 10:00:27
func coinChange(coins []int, amount int) int {
n := len(coins)
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, amount+1)
for j := range memo[i] {
memo[i][j] = -1 // -1 表示没有访问过
}
}
var dfs func(int, int) int
dfs = func(i, c int) (res int) {
if i < 0 {
if c == 0 {
return 0
}
return math.MaxInt / 2 // 除 2 是防止下面 + 1 溢出
}
p := &memo[i][c]
if *p != -1 {
return *p
}
defer func() { *p = res }()
if c < coins[i] {
return dfs(i-1, c)
}
return min(dfs(i-1, c), dfs(i, c-coins[i])+1)
}
ans := dfs(n-1, amount)
if ans < math.MaxInt/2 {
return ans
}
return -1
}
cpp 解法, 执行用时: 96 ms, 内存消耗: 14.4 MB, 提交时间: 2023-10-07 11:42:52
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int Max = amount + 1;
vector<int> dp(amount + 1, Max);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int j = 0; j < (int)coins.size(); ++j) {
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
java 解法, 执行用时: 12 ms, 内存消耗: 42.1 MB, 提交时间: 2023-10-07 11:42:38
public class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
python3 解法, 执行用时: 1152 ms, 内存消耗: 15.3 MB, 提交时间: 2022-08-10 14:45:38
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
python3 解法, 执行用时: 884 ms, 内存消耗: 50.3 MB, 提交时间: 2022-08-10 14:44:59
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
@functools.lru_cache(amount)
def dp(rem) -> int:
if rem < 0: return -1
if rem == 0: return 0
mini = int(1e9)
for coin in self.coins:
res = dp(rem - coin)
if res >= 0 and res < mini:
mini = res + 1
return mini if mini < int(1e9) else -1
self.coins = coins
if amount < 1: return 0
return dp(amount)