---

dp专题15 零钱兑换

原创 于 2024-01-19 17:01:37 发布 · 粉丝可见 · 502 阅读 · 6 · 5 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/135702241

本题链接： 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目：

思路：

这道题，是个比较模板的完全背包问题，这里要求的是问凑成总金额所需的最少的硬币的个数。

我们明确一下dp[ i ] 的含义，是   dp[ i ] 存储的是凑成总金额所需的最少的硬币的个数。

其中 下标 i 的含义是  “背包容量” amount ，  并且不同金额中是有无限个的。

所以我们可以将，不同金额硬币作为”物品体积”，每个硬币价值都为 1 表示物品的数量。

其次我们也要分析 dp 数组的初始化，由于 要求所需最少的硬币个数，所以我们将dp初始化全部为正无穷。 其中 dp[ 0 ] 要从初始化为 0  ，毕竟 凑成总金额为 0 所需的硬币个数就是 0.

随后确定 dp 公式：    dp[ j ] = min(dp[ j ] , dp[ j - i ] + 1 );

最后我们选取的过程中，选取顺序无关，所以是个组合数，确定遍历顺序。

先物品，后背包。

代码详解如下：

class Solution {
public:
    const int INF = 0x3f3f3f3f3f3f3f;   // 定义正无穷
    inline int coinChange(vector<int>& coins, int &amount) 
{
	vector<int>dp(amount + 2,INF);  // 开辟 dp 数组，并初始化为 INF
	dp[0] = 0;  // 特定初始化
	
    // 组合数的遍历物品以及背包
	for(int &i:coins)   
	{
		for(int j = i;j <= amount;++j)  // 完全背包正向遍历
		{
			dp[j] = min(dp[j],dp[j - i] + 1);   // dp 公式
		}
	}
	if(dp[amount] >= INF) return -1;    // 返回结果
	else return dp[amount];
}
};

最后提交：