本题链接：力扣（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 );
最后我们选取的过程中，选取顺序无关，所以是个组合数，确定遍历顺序。文章来源：https://www.toymoban.com/news/detail-805598.html
先物品，后背包。文章来源地址https://www.toymoban.com/news/detail-805598.html
代码详解如下：
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];
}
};最后提交：
到了这里，关于dp专题15 零钱兑换的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
