题目描述补充

题目：给定一个整数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 示例代码

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 示例代码

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 示例代码

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

码小课网站中有更多相关内容分享给大家学习，包括动态规划、贪心算法、回溯算法等经典算法问题的深入解析和代码实现，欢迎访问码小课获取更多知识。