LeetCode 算法：零钱兑换 c++

本文主要是介绍LeetCode 算法：零钱兑换 c++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接🔗：零钱兑换
难度：中等⭐️⭐️

题目

给你一个整数数组 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 <= coins.length <= 12
1 <= coins[i] <= 2³¹ - 1
0 <= amount <= 10⁴

题解

解题思路：

LeetCode上的“零钱兑换”问题是一个典型的动态规划问题。题目要求给定不同面额的硬币和一个总金额，求出组成总金额的最少硬币数。以下是这个问题的解题思路：

问题描述
给定不同面额的硬币和一个总金额。写出一个函数来计算可以组成总金额的最少硬币数。如果无法组成总金额，返回-1。

输入

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

输出

一个整数，表示组成总金额的最少硬币数。如果无法组成总金额，返回-1。

动态规划解题思路

定义状态：dp[i] 表示组成金额 i 所需的最少硬币数。

确定状态转移方程：

如果没有硬币或者金额为0，那么硬币数为0：dp[0] = 0
对于每个金额 i，我们尝试所有小于等于 i 的硬币面额 coin，更新状态：dp[i] = min(dp[i], dp[i - coin] + 1)

确定初始状态和边界条件：

初始化 dp 数组，大小为 amount + 1，所有元素设为一个足够大的数（比如 amount + 1），因为最少硬币数不会超过总金额。
dp[0] 初始化为0。

计算顺序：

从 1 到 amount 遍历每个金额，对于每个金额，遍历所有硬币面额，更新 dp[i]。

构造最优解：

如果 dp[amount] 仍然为初始化时的较大值，则表示无法组成该金额，返回-1。
否则，返回 dp[amount]。

c++ demo：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>using namespace std;// 动态规划求解零钱兑换问题的函数
int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, amount + 1); // 初始化为最大值dp[0] = 0; // 金额为0时，硬币数为0for (int i = 1; i <= amount; ++i) {for (int coin : coins) {if (i - coin >= 0) {dp[i] = min(dp[i], dp[i - coin] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];
}// 主函数，用于测试零钱兑换算法
int main() {vector<int> coins = { 1, 2, 5 }; // 硬币面额int amount = 11; // 总金额int result = coinChange(coins, amount);if (result != -1) {cout << "Minimum number of coins required: " << result << endl;}else {cout << "Not possible to make the amount with given coins" << endl;}return 0;
}