面试经典算法题76-零钱兑换

LeetCode.322

问题描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

思路

1. 初始化：

   • dp[0] 设为 0，因为凑成金额 0 需要 0 个硬币。

   • 其他的 dp 元素初始化为一个大值（例如 amount + 1），表示初始时认为无法凑成该金额。

2. 状态转移方程：对于每一个金额 i，遍历所有的硬币面额 coin：

   如果 i >= coin，则更新 dp[i] = min(dp[i], dp[i - coin] + 1)。

3. 返回结果：最终 dp[amount] 即为所需的最少硬币数。如果 dp[amount] 仍为初始值，说明无法凑成该金额，返回 -1。

参考代码

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 函数：计算最少硬币个数来凑成目标金额
int coinChange(vector<int>& coins, int amount) {
    // 创建一个大小为 amount+1 的数组 dp，初始值为 amount + 1（表示无法达到的高值）
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0; // 凑成金额 0 需要 0 个硬币

    // 遍历每个金额 i
    for (int i = 1; i <= amount; ++i) {
        // 遍历每个硬币面额
        for (int coin : coins) {
            // 如果当前金额 i 大于等于硬币面额 coin
            if (i >= coin) {
                // 状态转移方程：dp[i] = min(dp[i], dp[i - coin] + 1)
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // 如果 dp[amount] 大于 amount，表示无法凑成该金额，返回 -1；否则返回 dp[amount]
    return dp[amount] > amount ? -1 : dp[amount];
}

int main() {
    vector<int> coins1 = {1, 2, 5};
    int amount1 = 11;
    cout << "输入: coins = [1, 2, 5], amount = 11" << endl;
    cout << "输出: " << coinChange(coins1, amount1) << endl;  // 输出: 3

    vector<int> coins2 = {2};
    int amount2 = 3;
    cout << "输入: coins = [2], amount = 3" << endl;
    cout << "输出: " << coinChange(coins2, amount2) << endl;  // 输出: -1

    vector<int> coins3 = {1};
    int amount3 = 0;
    cout << "输入: coins = [1], amount = 0" << endl;
    cout << "输出: " << coinChange(coins3, amount3) << endl;  // 输出: 0

    return 0;
}

Java

import java.util.Arrays;

public class CoinChange {

    // 函数：计算最少硬币个数来凑成目标金额
    public int coinChange(int[] coins, int amount) {
        // 创建一个大小为 amount+1 的数组 dp，初始值为 amount + 1（表示无法达到的高值）
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0; // 凑成金额 0 需要 0 个硬币

        // 遍历每个金额 i
        for (int i = 1; i <= amount; ++i) {
            // 遍历每个硬币面额
            for (int coin : coins) {
                // 如果当前金额 i 大于等于硬币面额 coin
                if (i >= coin) {
                    // 状态转移方程：dp[i] = min(dp[i], dp[i - coin] + 1)
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        // 如果 dp[amount] 大于 amount，表示无法凑成该金额，返回 -1；否则返回 dp[amount]
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        CoinChange solution = new CoinChange();

        int[] coins1 = {1, 2, 5};
        int amount1 = 11;
        System.out.println("输入: coins = [1, 2, 5], amount = 11");
        System.out.println("输出: " + solution.coinChange(coins1, amount1));  // 输出: 3

        int[] coins2 = {2};
        int amount2 = 3;
        System.out.println("输入: coins = [2], amount = 3");
        System.out.println("输出: " + solution.coinChange(coins2, amount2));  // 输出: -1

        int[] coins3 = {1};
        int amount3 = 0;
        System.out.println("输入: coins = [1], amount = 0");
        System.out.println("输出: " + solution.coinChange(coins3, amount3));  // 输出: 0
    }
}

Python

def coinChange(coins, amount):
    # 创建一个大小为 amount+1 的数组 dp，初始值为 amount + 1（表示无法达到的高值）
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0  # 凑成金额 0 需要 0 个硬币

    # 遍历每个金额 i
    for i in range(1, amount + 1):
        # 遍历每个硬币面额
        for coin in coins:
            # 如果当前金额 i 大于等于硬币面额 coin
            if i >= coin:
                # 状态转移方程：dp[i] = min(dp[i], dp[i - coin] + 1)
                dp[i] = min(dp[i], dp[i - coin] + 1)

    # 如果 dp[amount] 大于 amount，表示无法凑成该金额，返回 -1；否则返回 dp[amount]
    return dp[amount] if dp[amount] <= amount else -1

if __name__ == "__main__":
    coins1 = [1, 2, 5]
    amount1 = 11
    print("输入: coins = [1, 2, 5], amount = 11")
    print("输出:", coinChange(coins1, amount1))  # 输出: 3

    coins2 = [2]
    amount2 = 3
    print("输入: coins = [2], amount = 3")
    print("输出:", coinChange(coins2, amount2))  # 输出: -1

    coins3 = [1]
    amount3 = 0
    print("输入: coins = [1], amount = 0")
    print("输出:", coinChange(coins3, amount3))  # 输出: 0