动态规划：最少硬币凑金额问题详解

LeetCode322给你一个整数数组coins表示不同面额的硬币以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。你可以认为每种硬币的数量是无限的。示例 1输入coins [1, 2, 5], amount 11输出3解释11 5 5 1示例 2输入coins [2], amount 3输出-1Python解法动态规划class Solution: def coinChange(self, coins: List[int], amount: int) - int: # INF代表一个不可能达到的硬币数量用来标记该金额无法凑出 # 最多全用1元硬币只需要amount枚amount1一定达不到充当无穷大 INF amount 1 # 创建dp数组dp[x]表示凑出金额x所需最少硬币数 # 数组长度amount1覆盖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枚amount1一定达不到标记无解 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) { // 两种方案取最小值 // 方案1dp[money]不使用当前硬币保持原有最优值 // 方案2dp[money - c] 1使用当前硬币先凑money-c再加1枚当前硬币 dp[money] Math.min(dp[money], dp[money - c] 1); } } } // 三元判断返回结果 // 若dp[amount]仍等于INF说明无法凑出目标金额返回题目规定的-1 // 若不等于INFdp[amount]就是凑出amount的最少硬币数量直接返回 return dp[amount] INF ? -1 : dp[amount]; } }C解法动态规划class Solution { public: int coinChange(vectorint coins, int amount) { // INF充当无穷大标记最多全用1元硬币仅需amount枚amount1不可能达到代表无解 int INF amount 1; // dp数组dp[money]表示凑出金额money需要的最少硬币数量 vectorint 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]; } };