题目描述

零钱兑换

给定一个金额（amount）和一个硬币种类列表（coins），其中每种硬币都有一个面额（代表该硬币的值），请计算可以凑成该金额所需的最少硬币个数。如果无法凑成该金额，则返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3
输出: -1

注意:

• 你可以假设每种硬币的数量是无限的。
• 题目要求的是使用硬币的最小数量，如果有多种组合方式，返回数量最少的那个。

PHP 示例代码

function coinChange($coins, $amount) {
    $dp = array_fill(0, $amount + 1, PHP_INT_MAX); // 初始化dp数组，初始值为最大整数
    $dp[0] = 0; // 金额为0时，不需要任何硬币

    for ($i = 1; $i <= $amount; $i++) {
        foreach ($coins as $coin) {
            if ($coin <= $i && $dp[$i - $coin] != PHP_INT_MAX) {
                $dp[$i] = min($dp[$i], $dp[$i - $coin] + 1);
            }
        }
    }

    return $dp[$amount] != PHP_INT_MAX ? $dp[$amount] : -1;
}

// 示例用法
$coins = [1, 2, 5];
$amount = 11;
echo coinChange($coins, $amount); // 输出 3

Python 示例代码

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# 示例用法
coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount))  # 输出 3

JavaScript 示例代码

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

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

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

// 示例用法
const coins = [1, 2, 5];
const amount = 11;
console.log(coinChange(coins, amount)); // 输出 3

这些示例代码都采用了动态规划的思想，通过填充一个dp数组来逐步计算最小硬币数。在码小课网站上，你可以深入学习更多关于动态规划及其应用的算法知识。