### 题目描述 **零钱兑换** 给定一个金额（`amount`）和一个硬币种类列表（`coins`），其中每种硬币都有一个面额（代表该硬币的值），请计算可以凑成该金额所需的最少硬币个数。如果无法凑成该金额，则返回 `-1`。 **示例 1**: ``` 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 ``` **示例 2**: ``` 输入: coins = [2], amount = 3 输出: -1 ``` **注意**: - 你可以假设每种硬币的数量是无限的。 - 题目要求的是使用硬币的最小数量，如果有多种组合方式，返回数量最少的那个。 ### PHP 示例代码 ```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 示例代码 ```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 示例代码 ```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`数组来逐步计算最小硬币数。在码小课网站上，你可以深入学习更多关于动态规划及其应用的算法知识。