题目描述

换硬币问题：给定一个整数金额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代码示例

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

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

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

码小课网站中有更多相关内容分享给大家学习，欢迎访问码小课网站，获取更多编程知识和面试技巧。