零钱兑换

题目要求

给定一个整数数组 coins，代表不同面额的硬币，以及一个整数 amount，代表需要凑成的总金额。要求编写一个算法，计算出凑成该总金额所需的最少硬币个数。如果无法凑出，则返回 -1。假设每种硬币的数量是无限的。

解题思路

这个问题是一个典型的动态规划问题，可以通过构建一个动态规划表来逐步求解。以下是解题的步骤：

初始化动态规划数组：创建一个长度为 amount + 1 的数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币个数。初始化 dp[0] = 0，因为凑成金额 0 不需要任何硬币，其余元素初始化为一个大数，表示初始状态下无法凑齐。
填充动态规划表：遍历金额从 1 到 amount，对于每个金额 i，遍历每个硬币面额 coin，如果 coin 小于或等于 i，则尝试用这个硬币来凑，更新 dp[i] 的值为 min(dp[i], dp[i - coin] + 1)。这里 dp[i - coin] + 1 表示如果前面的金额 i - coin 已经被凑齐了，那么只需要再加一个面额为 coin 的硬币即可凑齐金额 i。
返回结果：最后，检查 dp[amount] 的值，如果它不是初始化的大数，那么就返回 dp[amount]，表示最少硬币个数；如果仍然是大数，则返回 -1，表示无法凑齐。

这种方法的时间复杂度是 O(n*m)，其中 n 是金额 amount，m 是硬币种类数。空间复杂度是 O(n)，因为需要一个长度为 amount + 1 的数组来存储状态。

Golang 版本

package main

import (
	"fmt"
	"math"
)

func coinChange(coins []int, amount int) int {
	// 初始化dp数组，长度为amount+1，初始值为amount+1，因为最多的硬币数不会超过amount
	dp := make([]int, amount+1)
	for i := range dp {
		dp[i] = amount + 1
	}
	// base case，凑成金额0的硬币数为0
	dp[0] = 0

	// 外层循环遍历所有状态的所有取值
	for i := 1; i <= amount; i++ {
		// 内层循环遍历所有选择的最小值
		for _, coin := range coins {
			if i-coin >= 0 {
				dp[i] = min(dp[i], dp[i-coin]+1)
			}
		}
	}

	// 如果dp[amount]没有被更新，说明凑不出该金额，返回-1
	if dp[amount] == amount+1 {
		return -1
	}
	return dp[amount]
}

// 辅助函数，求两个整数的最小值
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	coins := []int{1, 2, 5}
	amount := 11
	fmt.Println("The minimum number of coins is:", coinChange(coins, amount))
}

这段代码定义了一个 coinChange 函数，它接受一个整数数组 coins 和一个整数 amount，返回凑成总金额所需的最少硬币个数。如果无法凑出，则返回 -1。在 main 函数中，我们给出了硬币数组和金额的示例，并调用 coinChange 函数来输出结果。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    int coinChange(std::vector<int>& coins, int amount) {
        std::vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; ++i) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = std::min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
};

int main() {
    Solution solution;
    std::vector<int> coins = {1, 2, 5};
    int amount = 11;
    std::cout << "The minimum number of coins is: " << solution.coinChange(coins, amount) << std::endl;
    return 0;
}

这段 C++代码定义了一个 Solution 类，其中包含了 coinChange 方法，该方法接受一个整数向量 coins 和一个整数 amount，返回凑成总金额所需的最少硬币个数。如果无法凑出，则返回 -1。在 main 函数中，我们创建了一个 Solution 对象，并给出了硬币向量和金额的示例，然后调用 coinChange 方法并输出结果。

Python 版本

def coinChange(coins, amount):
    # 初始化dp数组，长度为amount+1，初始值为amount+1，因为最多的硬币数不会超过amount
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0  # base case

    # 遍历所有金额，更新dp数组
    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    # 如果dp[amount]为初始值，则表示无法凑出，返回-1
    return dp[amount] if dp[amount] != amount + 1 else -1

# 示例
coins = [1, 2, 5]
amount = 11
print("The minimum number of coins is:", coinChange(coins, amount))

这段 Python 代码定义了一个 coinChange 函数，它接受一个整数列表 coins 和一个整数 amount，返回凑成总金额所需的最少硬币个数。如果无法凑出，则返回 -1。在代码的最后，我们给出了硬币列表和金额的示例，并调用 coinChange 函数来输出结果。

Java 版本

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        java.util.Arrays.fill(dp, max);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println("The minimum number of coins is: " + solution.coinChange(coins, amount));
    }
}

这段 Java 代码定义了一个 Solution 类，其中包含了 coinChange 方法，该方法接受一个整数数组 coins 和一个整数 amount，返回凑成总金额所需的最少硬币个数。如果无法凑出，则返回 -1。在 main 方法中，我们创建了一个 Solution 对象，并给出了硬币数组和金额的示例，然后调用 coinChange 方法并输出结果。

Rust 版本

fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
    let mut dp = vec![amount + 1; (amount + 1) as usize];
    dp[0] = 0;

    for i in 1..=amount as usize {
        for &coin in &coins {
            if coin as usize <= i {
                dp[i] = dp[i].min(dp[i - coin as usize] + 1);
            }
        }
    }

    if dp[amount as usize] > amount {
        -1
    } else {
        dp[amount as usize]
    }
}

fn main() {
    let coins = vec![1, 2, 5];
    let amount = 11;
    println!("The minimum number of coins is: {}", coin_change(coins, amount));
}

这段 Rust 代码定义了一个 coin_change 函数，它接受一个整数向量 coins 和一个整数 amount，返回凑成总金额所需的最少硬币个数。如果无法凑出，则返回 -1。在 main 函数中，我们创建了硬币向量和金额的示例，并调用 coin_change 函数来输出结果。

总结

上述问题是一个经典的动态规划问题，通常被称为硬币找零问题。解决这个问题的核心思想是构建一个数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币数量。动态规划的转移方程是：

dp[i] = min(dp[i], dp[i - coin] + 1) for each coin in coins

这个方程意味着，要得到金额 i 的最少硬币数，我们应该查看每一个小于 i 的金额 j = i - coin，并且 j 加上一枚面值为 coin 的硬币。我们在所有可能的 coin 中选择最小的 dp[i - coin] + 1 作为 dp[i] 的值。

初始化时，dp[0] 被设置为 0，因为凑成金额 0 所需的硬币数显然是 0。其他的 dp[i] 初始化为一个大数，通常是金额 amount 加 1，这是因为最坏的情况下，凑成金额 i 的硬币数不会超过 i（全用面值为 1 的硬币）。

最后，如果 dp[amount] 仍然是初始化的大数，这意味着没有任何硬币组合能够凑成总金额，因此返回 -1。否则，dp[amount] 就是凑成总金额所需的最少硬币个数。

在不同的编程语言中，这个算法的实现细节可能略有不同，但核心逻辑是一致的。我们提供了 C++, Python, Java, 和 Rust 版本的代码实现，每种语言都遵循了上述动态规划的策略。

hot-100