LeetCode原题链接

原题

给你一个整数数组 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 <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

这道题目是经典的“找零钱”问题，在实际生活中非常常见。例如，在超市收银台，我们需要用最少的硬币组合来找零。在计算机科学中，这类问题通常可以抽象为如何从给定的一组物品中，选择最少数量的物品来达到某个目标值。它属于组合优化问题的一种，在金融、物流等领域都有潜在的应用。

审题

在面试中遇到这类问题时，我们首先要和面试官进行充分的沟通，明确题目的所有细节和限制条件。我们可以这样提问：

• 输入格式是什么？ coins 数组中的硬币面额是正整数吗？amount 是非负整数吗？
• 输出格式是什么？ 如果无法凑成总金额，是返回 -1 吗？
• 硬币数量是无限的吗？ 题目中已经明确说明“每种硬币的数量是无限的”，这很重要，意味着我们可以重复使用同一种面额的硬币。
• coins 数组中是否会有重复的面额？ 如果有重复，是否需要去重处理？（根据题目描述，通常不会有重复，即使有，动态规划也能处理，但明确一下更好）
• amount 为 0 的情况如何处理？ 示例 3 已经给出，amount 为 0 时，需要 0 个硬币，这是边界情况。
• coins 数组为空或者 amount 为负数的情况需要考虑吗？ 根据提示，coins.length 至少为 1，amount 至少为 0，所以不需要考虑这些情况。

通过这些提问，我们能够清晰地了解到：

• 输入： 一个整数数组 coins (硬币面额，正整数，数量无限)，一个整数 amount (总金额，非负整数)。
• 输出： 凑成 amount 所需的最少硬币个数，如果无法凑成则返回 -1。
• 约束： coins 数组长度在 1 到 12 之间，硬币面额在 1 到 2^31 - 1 之间，amount 在 0 到 10^4 之间。

解析

思路概述

这道题目是典型的动态规划问题。我们要求的是“最少硬币个数”，这通常会让我们联想到动态规划。动态规划的核心思想是将一个大问题分解成若干个相互关联的子问题，然后通过解决子问题来推导出大问题的解。

对于这道题，我们可以定义 dp[i] 为凑成金额 i 所需的最少硬币个数。我们的目标就是求 dp[amount]。

那么，dp[i] 如何从子问题推导出来呢？

假设我们要凑成金额 i。我们可以尝试使用每一种硬币 coin。如果我们使用了 coin 这个硬币，那么剩下的金额就是 i - coin。此时，我们只需要知道凑成 i - coin 所需的最少硬币个数 dp[i - coin]，那么凑成 i 的硬币个数就是 dp[i - coin] + 1（加 1 是因为我们用了一个 coin）。

由于我们可以使用任何一种硬币，所以 dp[i] 应该是所有 (dp[i - coin] + 1) 中的最小值。

状态转移方程： dp[i] = min(dp[i], dp[i - coin] + 1)，其中 coin 遍历 coins 数组中的所有硬币。

基地情况： dp[0] = 0，因为凑成金额 0 不需要任何硬币。

初始化： 由于我们要求最小值，所以 dp 数组中的其他元素需要初始化为一个足够大的值（例如 amount + 1 或者 Infinity），表示当前金额无法凑成。

（此处应为动态规划示意图，展示dp数组的填充过程和状态转移）

算法步骤

1. 初始化 dp 数组： 创建一个大小为 amount + 1 的数组 dp，并将所有元素初始化为 amount + 1（一个比任何可能结果都大的值，表示无法凑成）。将 dp[0] 设置为 0，表示凑成金额 0 需要 0 个硬币。
2. 遍历金额： 从 i = 1 到 amount 遍历每一个金额 i。
3. 遍历硬币： 对于每一个金额 i，遍历 coins 数组中的每一个硬币 coin。
4. 状态转移： 如果 i - coin 大于等于 0（即当前金额 i 可以减去 coin），则更新 dp[i] = min(dp[i], dp[i - coin] + 1)。
5. 返回结果： 最终，dp[amount] 就是凑成总金额 amount 所需的最少硬币个数。如果 dp[amount] 仍然是初始化的那个大值，说明无法凑成，返回 -1。

源码

核心代码模式

Java

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 coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

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

Python

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [float(\'inf\')] * (amount + 1)
        dp[0] = 0

        for i in range(1, amount + 1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        
        return dp[amount] if dp[amount] != float(\'inf\') else -1

JavaScript

var coinChange = function(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (i - coin >= 0) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
};

Go

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1 // Initialize with a value greater than amount
    }
    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)
            }
        }
    }

    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

ACM模式

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    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 coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

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

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Main sol = new Main();

        // Read coins
        int numCoins = scanner.nextInt();
        int[] coins = new int[numCoins];
        for (int i = 0; i < numCoins; i++) {
            coins[i] = scanner.nextInt();
        }

        // Read amount
        int amount = scanner.nextInt();

        int result = sol.coinChange(coins, amount);
        System.out.println(result);

        scanner.close();
    }
}

Python

import sys

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0

        for i in range(1, amount + 1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        
        return dp[amount] if dp[amount] != float("inf") else -1

if __name__ == "__main__":
    sol = Solution()
    # Example usage (ACM mode expects input from stdin)
    # For testing, you can provide input like:
    # 3
    # 1 2 5
    # 11
    # Or:
    # 1
    # 2
    # 3
    
    # Read coins
    num_coins = int(sys.stdin.readline())
    coins_str = sys.stdin.readline().split()
    coins = [int(x) for x in coins_str]
    
    # Read amount
    amount = int(sys.stdin.readline())
    
    result = sol.coinChange(coins, amount);
    print(result)

JavaScript

const coinChange = (coins, amount) => {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (i - coin >= 0) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
};

// ACM mode input/output
const readline = require(\'readline\');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];
rl.on(\'line\', (line) => {
    input.push(line);
}).on(\'close\', () => {
    const numCoins = parseInt(input[0]);
    const coins = input[1].split(\' \').map(Number);
    const amount = parseInt(input[2]);

    const result = coinChange(coins, amount);
    console.log(result);
});

Go

package main

import (
	"fmt"
	"bufio"
	"os"
	"strconv"
	"strings"
)

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1 // Initialize with a value greater than amount
    }
    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)
            }
        }
    }

    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	numCoins, _ := strconv.Atoi(scanner.Text())

	scanner.Scan()
	coinsStr := strings.Fields(scanner.Text())
	coins := make([]int, numCoins)
	for i, s := range coinsStr {
		coins[i], _ = strconv.Atoi(s)
	}

	scanner.Scan()
	amount, _ := strconv.Atoi(scanner.Text())

	result := coinChange(coins, amount)
	fmt.Println(result)
}

面试官追问

仅仅通过了测试用例，并不意味着我们对问题有了深入的理解。在面试中，面试官可能会进一步提问，以考察我们对算法的掌握程度和解决问题的能力。我们来模拟一下面试官的追问：

• 该算法的时间复杂度和空间复杂度是多少？如何计算的？

  • 时间复杂度： O(amount * N)，其中 amount 是目标金额，N 是硬币面额的数量。外层循环遍历 amount 次，内层循环遍历 N 次硬币面额。因此，总的时间复杂度是 amount 乘以 N。
  • 空间复杂度： O(amount)。我们创建了一个 dp 数组，其大小与 amount 相关。因此，空间复杂度是 amount 的线性关系。

• 该算法的核心思想是什么？

  该算法的核心思想是动态规划。我们将原始问题分解为更小的子问题，即“凑成金额 i 所需的最少硬币数”。通过构建 dp 数组，我们从 dp[0] 开始，逐步推导出 dp[amount]。每个 dp[i] 的值都依赖于 dp[i - coin] 的值，这体现了动态规划的“无后效性”和“最优子结构”特性。

• 为什么选择这种解法而不是其他方法？

  对于这类求“最值”（最少、最多）的问题，并且问题具有“最优子结构”和“重叠子问题”的特点时，动态规划通常是首选。回溯法（或暴力递归）虽然也能解决，但会存在大量的重复计算，导致时间复杂度非常高，通常会超时。贪心算法在这道题中不适用，因为贪心策略（每次都选择面额最大的硬币）不一定能得到最优解，例如 coins = [1, 3, 4], amount = 6，贪心会选择 4 + 1 + 1 = 3 个硬币，而最优解是 3 + 3 = 2 个硬币。

结语

“零钱兑换”问题是动态规划的经典入门题目，它很好地展示了动态规划在解决最优化问题中的强大能力。通过这道题，我们学习了如何定义状态、推导状态转移方程、确定基地情况以及进行初始化。在实际开发中，我们常常会遇到类似的优化问题，例如资源分配、任务调度等，动态规划的思想都能为我们提供宝贵的解决思路。掌握动态规划，不仅能帮助我们应对算法面试，更能提升我们解决复杂问题的能力。