[数据结构与算法]LeetCode322. [零钱兑换] C++实现

写在前面

从本篇文章开始，将开启一个新的系列，用以讲解LeetCode题目，并用C++编程语言实现之。

本篇讲解的是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

解题思路

本题的解题过程中用到了递归的思想（递归的典型案例是求斐波那契数列的问题），我们不妨假设当前的目标金额是n，至少需要 dp(n) 个硬币可以凑出该金额；dp(i) 为组成金额 i 所需的最少的硬币数量，则有²：

其中，Cj代表第 j 枚硬币的面值。

为了方便理解，我们不妨举个栗子，如下面草图所示：

实现过程

C++实现

#include<stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>

/*
Leetcode-322-零钱兑换  题目描述
给定不同面额的硬币 coins 和一个总金额 amount
编写一个函数来计算可以凑成总金额所需的最少的硬币个数
如果没有任何一种硬币组合能组成总金额，返回 -1
*/

int coinChange(std::vector<int> coins, int amount) {
	//因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），
	//所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值。

	//定义(amount + 1)个整型元素的向量,且给每个元素的初值为(amount + 1)
	std::vector <int> dp(amount + 1, amount + 1);    // dp(i) 为组成金额 i 所需的最少的硬币数量
	//std::vector <int> dp(amount, amount);
	dp[0] = 0;

	for (int i = 1; i <= amount; i++)   // 金额i
	{
		for (int j = 0; j < (int)coins.size(); j++)   // 第j枚硬币
		{
			if (coins[j] <= i)     // coins[j]? 代表的是第 j 枚硬币的面值
				dp[i] = std::min(dp[i], dp[i - coins[j]] + 1);
				//dp[i] = std::min(dp[i - coins[j]] + 1);
		}
	}
	return dp[amount] > amount ? -1 : dp[amount];
}

int main(){
	int result = coinChange({1,2,5}, 11);  // 即分别有面值为1、2、5的硬币，要求凑齐的总金额为11， 输出结果为3
	// int result = coinChange({ 1,2,3 }, 6);  // 输出结果为2
	std::cout << result << std::endl;
	return 0;
}

输出结果

3
请按任意键继续. . .

代码讲解

现针对该代码，进行讲解：

本题目所要求的为凑齐指定金额 amount 所需的最少硬币数 dp[amount]；定义两个变量进行双层循环，其一是所给的各种面额的硬币种类数 j ，另一个是需要凑齐的总金额 i；其中，变量 i 从1开始遍历至所要凑齐的总金额；变量 j 从0开始（即第1种类型面额的硬币）遍历至所给的所有面额的硬币种类数；判断条件为，如果当前类别硬币的面额数值 coins[j] 小于或等于要凑齐的总金额，那么最少硬币数dp[i] 为 min(dp[i], dp[i- coins[j]] +1)，也即选取当前和上一个递归循环两者中的最小值。

上述解体思路及实现过程仅供参考，如有错误，请批评指正。如果我的这篇文章帮助到了你，那我也会感到很高兴，一个人能走多远，在于与谁同行。

参考