动态规划：最少硬币凑金额问题详解
LeetCode322
给你一个整数数组coins，表示不同面额的硬币；以及一个整数amount，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins =[1, 2, 5], amount =11
输出：3
解释：11 = 5 + 5 + 1
示例 2：输入：coins =[2], amount =3
输出：-1
Python解法
动态规划
class Solution: def coinChange(self, coins: List[int], amount: int) -> int: # INF：代表一个不可能达到的硬币数量，用来标记该金额无法凑出 # 最多全用1元硬币只需要amount枚，amount+1一定达不到，充当无穷大 INF = amount + 1 # 创建dp数组，dp[x]表示凑出金额x所需最少硬币数 # 数组长度amount+1，覆盖0~amount所有金额，初始全部填充INF（默认都凑不出来） dp = [INF] * (amount + 1) # 边界条件：金额为0时，不需要任何硬币，硬币数量为0 dp[0] = 0 # 外层循环：遍历从1到amount的每一个目标金额，逐个计算最少硬币 for i in range(1, amount + 1): # 内层循环：尝试每一种硬币，看能否用当前硬币更新dp[i] for coin in coins: # 当前硬币面额不能大于当前要凑的金额i，否则不能选这枚硬币 if coin <= i: # 两种选择取最小值： # 1. dp[i]：不选当前硬币，维持原来的最少硬币数 # 2. dp[i - coin] + 1：选当前硬币，先凑i-coin，再加这1枚硬币 dp[i] = min(dp[i], dp[i - coin] + 1) # 判断最终结果： # 如果dp[amount]还是INF，说明无法凑出目标金额，返回题目要求的-1 # 否则dp[amount]就是凑出amount的最少硬币数量，直接返回 return -1 if dp[amount] == INF else dp[amount]Java解法
动态规划
class Solution { public int coinChange(int[] coins, int amount) { // INF 充当无穷大，最多全1元硬币只需amount枚，amount+1一定达不到，标记无解 int INF = amount + 1; // dp数组：dp[money] = 凑出金额money所需最少硬币数量 int[] dp = new int[amount + 1]; // 全部初始化为无解标记INF Arrays.fill(dp, INF); // 边界条件：金额0，不需要硬币，数量为0 dp[0] = 0; // 外层循环：依次计算1 ~ amount每一个金额的最少硬币数 for (int money = 1; money <= amount; money++) { // 内层循环：遍历每一种硬币，尝试用该硬币更新当前金额的最优解 for (int c : coins) { // 硬币面额不能超过当前要凑的金额，否则无法选取该硬币 if (money >= c) { // 两种方案取最小值： // 方案1：dp[money]，不使用当前硬币，保持原有最优值 // 方案2：dp[money - c] + 1，使用当前硬币，先凑money-c，再加1枚当前硬币 dp[money] = Math.min(dp[money], dp[money - c] + 1); } } } // 三元判断返回结果： // 若dp[amount]仍等于INF，说明无法凑出目标金额，返回题目规定的-1 // 若不等于INF，dp[amount]就是凑出amount的最少硬币数量，直接返回 return dp[amount] == INF ? -1 : dp[amount]; } }C++解法
动态规划
class Solution { public: int coinChange(vector<int>& coins, int amount) { // INF充当无穷大标记，最多全用1元硬币仅需amount枚，amount+1不可能达到，代表无解 int INF = amount + 1; // dp数组：dp[money]表示凑出金额money需要的最少硬币数量 vector<int> dp(amount + 1, INF); // 边界条件：金额为0时，不需要任何硬币，硬币数为0 dp[0] = 0; // 外层循环：逐个计算1 ~ amount所有金额的最少硬币数 for (int money = 1; money <= amount; money++) { // 内层循环：遍历每一种硬币，尝试用当前硬币更新最优解 for (int c : coins) { // 硬币面额不能超过当前要凑的金额，否则无法选用该硬币 if (money >= c) { // 两种方案取更小值： // 1. dp[money]：不选当前硬币，保留原有最优硬币数 // 2. dp[money - c] + 1：选当前硬币，凑完money-c后再加这一枚硬币 dp[money] = min(dp[money], dp[money - c] + 1); } } } // 三元表达式返回结果： // dp[amount]等于INF说明无法凑出目标金额，返回-1；否则返回最少硬币数量 return dp[amount] == INF ? -1 : dp[amount]; } };