dp专题15 零钱兑换

本题链接：力扣（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];
}
};

?最后提交：