当前位置： 面试刷题>> 换硬币 (经典算法题500道)
### 题目描述
**换硬币问题**：给定一个整数金额`amount`，以及一组硬币的币值列表`coins`，每种硬币的数量都是无限的。计算并返回凑成这个金额所需的最少硬币数量。如果无法凑成，则返回-1。
### 示例
**输入**:
- `amount`: 11
- `coins`: [1, 2, 5]
**输出**: 3
**解释**: 11 = 5 + 5 + 1
### 解题思路
这个问题是一个典型的动态规划问题。我们可以定义一个数组`dp`，其中`dp[i]`表示凑成金额`i`所需的最少硬币数量。初始化`dp[0] = 0`，表示凑成金额为0所需的最少硬币数量为0。对于其他的`dp[i]`，我们从`coins`中的每种硬币开始尝试，看哪种方式可以使得`dp[i]`最小。
### PHP代码示例
```php
function coinChange($amount, $coins) {
$dp = array_fill(0, $amount + 1, PHP_INT_MAX);
$dp[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;
}
// 测试用例
$amount = 11;
$coins = [1, 2, 5];
echo coinChange($amount, $coins); // 输出: 3
```
### Python代码示例
```python
def coinChange(amount, coins):
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
# 测试用例
amount = 11
coins = [1, 2, 5]
print(coinChange(amount, coins)) # 输出: 3
```
### JavaScript代码示例
```javascript
function coinChange(amount, coins) {
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 amount = 11;
const coins = [1, 2, 5];
console.log(coinChange(amount, coins)); // 输出: 3
```
**码小课网站中有更多相关内容分享给大家学习**，欢迎访问码小课网站，获取更多编程知识和面试技巧。