目标金额是否能被给定硬币组成或者最少硬币数量

在编程中判断一个目标金额能否由一组给定的硬币组成这是一个经典的“硬币找零”或“完全背包”问题。最常用且高效的解决方法是使用动态规划核心思路将这个问题分解成更小的子问题。是不是在想当前金额怎么知道能够由哪些已知硬币凑成呢实际上可以枚举每一种面值的硬币例如使用了面值为coin的硬币那么问题就转化为能否凑出i-coin。只要i-coin能凑出那么金额i也能被凑出。解决方案布尔型动态规划这种方法直接判断能还是不能。定义状态创建一个布尔数组dp其中dp[i]表示金额i是否可以被凑出初始化dp[0] true表示金额0总是可以被凑出什么硬币都不用其余dp[i]初始化为false状态转移遍历每一种硬币对于每个硬币coin更新所有大于等于coin的金额i的状态。状态转移方程dp[i] dp[i] || dp[i-coin]状态转移的意思即金额i能够被凑出要么是他之前就已经能被凑出要么是使用了当前这枚硬币后剩下的金额i - coin能被凑出。代码实现importjava.util.Arrays;publicclassCoinChangeCheck{publicstaticbooleancanMakeAmount(int[]coins,intamount){// 1. 创建并初始化 dp 数组boolean[]dpnewboolean[amount1];dp[0]true;// 金额0总是可以凑出// 2. 遍历每种硬币for(intcoin:coins){// 3. 更新所有可能受当前硬币影响的金额for(inticoin;iamount;i){// 如果金额 i-coin 可以被凑出那么金额 i 也可以被凑出dp[i]dp[i]||dp[i-coin];}}// 4. 返回目标金额是否可以被凑出returndp[amount];}publicstaticvoidmain(String[]args){int[]coins1{1,2,5};intamount111;System.out.println(硬币 Arrays.toString(coins1) 能否凑出 amount1? canMakeAmount(coins1,amount1));// 输出: trueint[]coins2{2};intamount23;System.out.println(硬币 Arrays.toString(coins2) 能否凑出 amount2? canMakeAmount(coins2,amount2));// 输出: false}}计算最少需要多少枚硬币延续刚刚的思路只需稍作修改不仅知道能不能还能知道“最少需要多少个”。定义状态创建一个整型数组dp其中dp[i]表示凑出金额i所需的最少硬币数量初始化dp[0] 0,凑出金额0需要0个硬币dp[i]可以初始化为一个“不可能的大数”代表初始时无法凑出状态转移dp[i] Math.min(dp[i], dp[i-coin]1)表示凑出金额i的最少硬币数是不使用当前coin硬币或者使用当前coin硬币dp[i - coin] 1classSolution{publicintcoinChange(int[]coins,intamount){// 初始化dpint[]dpnewint[amount1];// 先赋予一个较大的值// Arrays.fill(dp, Integer.MAX_VALUE);Arrays.fill(dp,amount1);dp[0]0;// 枚举硬币for(intcoin:coins){// 更新所有可能受当前硬币影响的金额for(inticoin;iamount;i){dp[i]Math.min(dp[i],dp[i-coin]1);}}// for (int i 1; i amount; i) {// for (int j 0; j coins.length; j){// if (coins[j] i) {// dp[i] Math.min(dp[i], dp[i - coins[j]]1);// }// }// }// 最终如果dp[amount]仍然是较大值说明凑不出来返回-1returndp[amount]amount?-1:dp[amount];}}假设是0-1背包问题问题类型硬币数量假设内层循环顺序核心思想完全背包 (我提供的解法)无限从小到大 (coin→amount)允许重复使用当前物品0-1背包一个从大到小 (amount→coin)保证每个物品只用一次