零钱兑换

给你一个整数数组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

这题思路也是动态规划，对于当前第i个硬币，我们可以选择拿或者不拿。拿的话，那么当前的硬币数就是dp[i-1][j-coins[i]]+1，不拿的话，那么当前的硬币数就是dp[i-1][j]。那么我们可以得到状态方程：

$$dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]]+1)$$

那么递归边界条件是什么呢： $dp[i][0] = 0$ 第0个硬币，凑成0元，需要0个硬币 $dp[0][j] = \infty$ 第0个硬币，凑成j元，需要$\infty$个硬币 那么动态规划中，只需要保留两个参数，一个是第i个硬币，另一个是凑成j元需要的硬币数。下面看代码：

class Solution {
public:
    /**
     * @brief 计算凑成指定金额所需的最少硬币个数
     * 
     * @param coins 不同面额的硬币数组
     * @param amount 要凑成的总金额
     * @return int 凑成总金额所需的最少硬币个数，如果无法凑成则返回 -1
     */
    int coinChange(vector<int>& coins, int amount) {
        // 获取硬币数组的长度
        int n = coins.size();
        // 创建一个二维数组visited，用于记录已经计算过的状态，初始值为 -1
        vector visited(n, vector<int>(amount + 1, -1));
        // 定义一个递归函数dfs，用于计算从第i个硬币开始凑成金额c所需的最少硬币个数
        function<int(int, int)> dfs = [&](int i, int c) {
            // 当金额为0时，不需要任何硬币，返回0
            if (c == 0) {
                return 0; 
            }
            // 没有硬币可选的情况，返回一个较大的数表示不可能
            if (i < 0) {
                return INT_MAX / 2;
            } 
            // 引用visited数组中当前状态的结果
            auto& res = visited[i][c];
            // 如果该状态已经计算过，直接返回结果
            if (res != -1) {
                return res;
            }

            // 如果当前金额小于第i个硬币的面额，无法使用该硬币，递归计算前i-1个硬币凑成金额c所需的最少硬币个数
            if (c < coins[i]) {
                return dfs(i - 1, c);
            }
            // 否则，计算不使用第i个硬币和使用第i个硬币所需的最少硬币个数的最小值
            return res = min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);
        };
        // 调用递归函数，从最后一个硬币开始计算凑成总金额所需的最少硬币个数
        int res = dfs(n - 1, amount);
        // 如果结果小于 INT_MAX/2，说明可以凑成总金额，返回结果；否则返回 -1
        return res < INT_MAX/2 ? res : -1;
    }

};

零钱兑换2

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

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]

输出：4

解释：有四种方式可以凑成总金额：

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]

输出：0

解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10]

输出：1

这题思路和上题差不多，主要递归边界和条件直接给出代码

class Solution {
public:
    /**
     * @brief 计算凑成指定金额的硬币组合数
     * 
     * @param amount 要凑成的总金额
     * @param coins 不同面额的硬币数组
     * @return int 凑成总金额的硬币组合数
     */
    int change(int amount, vector<int>& coins) {
        // 获取硬币数组的长度
        int n = coins.size();
        // 创建一个二维数组visited，用于记录已经计算过的状态，初始值为-1
        vector visited(n, vector<int>(amount + 1, -1));

        // 定义一个递归函数dfs，用于计算从第i个硬币开始凑成金额c的组合数
        function<int(int,int)> dfs = [&](int i, int c) {
            // 如果当前金额为0，说明找到了一种组合，返回1
            if (c == 0) return 1;
            // 如果没有硬币可选，无法凑成金额，返回0
            if (i < 0) return 0;

            // 引用visited数组中当前状态的结果
            auto& res = visited[i][c];
            // 如果该状态已经计算过，直接返回结果
            if (res != -1) {
                return res;
            }

            // 如果当前金额小于第i个硬币的面额，无法使用该硬币，递归计算前i-1个硬币凑成金额c的组合数
            if (c < coins[i]) {
                return dfs(i - 1, c);
            }
            // 否则，计算使用和不使用第i个硬币的组合数之和
            return res = (dfs(i - 1, c) + dfs(i, c - coins[i]));
        };

        // 调用递归函数，从最后一个硬币开始计算凑成总金额的组合数
        auto res = dfs(n - 1, amount);
        // 返回最终结果
        return res;
    }

};

更新日志

2025/3/2 09:12

查看所有更新日志

• 041c6-update tencent interview于 2025/3/2