一、求换零钱的最大次数
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
public static int change(int amount, int[] coins) { int[] dp = new int[amount+1]; dp[0] = 1; for (int coin : coins) { for (int j = 1; j <= amount; j++) { if (j >= coin) { dp[j] = dp[j] + dp[j - coin]; } } } Arrays.sort(dp); return dp[dp.length-1]; }
二、求换零钱最少的硬币个数
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
输入：coins = [2], amount = 3
输出：-1
输入：coins = [1], amount = 0
输出：0
public static int coinChange(int[] coins, int amount) { //初始化dp表，最大值目标最大值 + 1,相当于无穷大 int max = amount + 1; int[] dp = new int[amount + 1]; //初始化dp表里面数据全部为max Arrays.fill(dp, max); //已知目标金额为0的时候，需要0个硬币 dp[0] = 0; //遍历1到amount需要多少硬币 for(int i = 1; i <= amount; i++) { //遍历所有硬币 for(int coin : coins) { if(i - coin < 0) continue; //子问题dp[i-coin]加1枚硬币就是当前硬币的需要个数 dp[i] = Math.min(dp[i], dp[i-coin] + 1); } } //如果目标金额的一直没有答案返回-1 return dp[amount] == max ? -1 : dp[amount]; }
