当前位置： 面试刷题>> 凑n分钱的方案数 (经典算法题500道)
### 题目描述补充
**题目**：给定一个整数`n`（表示金额）和一组不同的硬币面值`coins`（每个元素代表一个硬币的面值），计算并返回凑成总金额`n`的不同方式的数目。每种硬币可以使用多次，且不考虑顺序（即，`[1, 5, 1]`和`[1, 1, 5]`被视为同一种方式）。
**示例**：
- 输入：`n = 5, coins = [1, 2, 5]`
- 输出：`4`
- 解释：有四种方式可以凑成5分：`[5]`、`[1, 1, 1, 1, 1]`、`[1, 1, 2, 1]`、`[2, 2, 1]`
### PHP 示例代码
```php
function coinChange($n, $coins) {
$dp = array_fill(0, $n + 1, 0);
$dp[0] = 1; // 没有金额时，有一种方式：不选任何硬币
for ($i = 1; $i <= $n; $i++) {
for ($j = 0; $j < count($coins); $j++) {
if ($coins[$j] <= $i) {
$dp[$i] += $dp[$i - $coins[$j]];
}
}
}
return $dp[$n];
}
// 测试
$n = 5;
$coins = [1, 2, 5];
echo coinChange($n, $coins); // 输出: 4
```
### Python 示例代码
```python
def coinChange(n, coins):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for coin in coins:
if coin <= i:
dp[i] += dp[i - coin]
return dp[n]
# 测试
n = 5
coins = [1, 2, 5]
print(coinChange(n, coins)) # 输出: 4
```
### JavaScript 示例代码
```javascript
function coinChange(n, coins) {
const dp = new Array(n + 1).fill(0);
dp[0] = 1; // 没有金额时，有一种方式：不选任何硬币
for (let i = 1; i <= n; i++) {
for (let j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] += dp[i - coins[j]];
}
}
}
return dp[n];
}
// 测试
const n = 5;
const coins = [1, 2, 5];
console.log(coinChange(n, coins)); // 输出: 4
```
**码小课网站中有更多相关内容分享给大家学习**，包括动态规划、贪心算法、回溯算法等经典算法问题的深入解析和代码实现，欢迎访问码小课获取更多知识。