本文共 2948 字，大约阅读时间需要 9 分钟。

LeetCode第322题。

题目描述:

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

例子：

输入: coins = [1, 2, 5], amount = 11输出: 3 解释: 11 = 5 + 5 + 1

解题：

一、思路：动态规划；

1.dp[i]表示amount = i时，需要的硬币数量；填充dp[],因为dp[]最大为amount个，所以将其初始化为amount+1；

2.动态方程：dp[i] = Math.max(dp[i], dp[i - coins[j]] + 1)；当前金额i所使用的金币个数，是dp[i] 和i - coin[j]金额所使用的金币个数dp[i - coin[i]] + 1，这里加一是因为coin[i]，消耗一个金币。

public class Solution {  public int coinChange(int[] coins, int amount) {    int max = amount + 1;     //dp[i] 表示amount = i时，需要的硬币数量    int[] dp = new int[amount + 1];//dp[0] 到 dp[amount]     //填充dp[],因为dp[]最大为amount个，所以将其初始化为amount+1    Arrays.fill(dp, max);    dp[0] = 0;    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);        }      }    }    return dp[amount] > amount ? -1 : dp[amount];  }}

二、思路：递归；

1.先将硬币面额排序, 用最大面额的金币去组成amount。剩余amount1 = amount - n * coins[coins.length - 1];此时需要n个金币。

2.剩余金额在用剩余面额硬币兑换，再考虑用coins.length - 2个最大面额硬币, 剩余金额在用剩余面额硬币兑换。【此处需要考虑，如果剩下面额金币，不能兑换amount1呢？此时需要，将 amount1 变更为amount1 = amount - (n-1) * coins[coins.length - 1]】再继续用剩余的金币面额去兑换。

class Solution {	int miniAns;	public int coinChange(int[] coins, int amount) {		if (amount == 0) return 0;		Arrays.sort(coins);		miniAns = Integer.MAX_VALUE;		coinChangeL(coins, amount, coins.length - 1, 0);		miniAns = miniAns == Integer.MAX_VALUE? -1: miniAns;		return miniAns;	}	public void coinChangeL(int[] coins, int amount, int index, int cnt) {		if (amount == 0) {			miniAns = Math.min(cnt, miniAns);			return;		}		if (index < 0 || amount < 0) {			return;		}		for (int maxcoin = amount/coins[index]; maxcoin >= 0 && maxcoin + cnt < miniAns; maxcoin--) {			coinChangeL(coins, amount - maxcoin * coins[index], index - 1, cnt + maxcoin);		}	}}

进阶-题目描述：

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 

例子：

输入: amount = 5, coins = [1, 2, 5]输出: 4解释: 有四种方式可以凑成总金额:5=55=2+2+15=2+1+1+15=1+1+1+1+1

解答：

1.动态规划

思路：

1.状态：dp[i]表示金额i的组成次数。很明显当amount=0时，dp[0] = 1；

2.动态方程：dp[i] = dp[i] + dp[i - coins[j]]；

class Solution {  public int change(int amount, int[] coins) {    int[] dp = new int[amount + 1];    dp[0] = 1;    for (int coin : coins) {      for (int x = coin; x < amount + 1; ++x) {        dp[x] += dp[x - coin];      }    }    return dp[amount];  }}

2.递归法

超时。

class Solution {    int res;    public int change(int amount, int[] coins) {		if (amount == 0 ) return 1;		Arrays.sort(coins);        res = 0;		coinChangeL(coins, amount, coins.length - 1, 0);		return res;    }    public void coinChangeL(int[] coins, int amount, int index, int cnt) {		if (amount == 0) {            res++;			return;		}		if (index < 0 || amount < 0) {			return;		}		for (int maxcoin = amount/coins[index]; maxcoin >= 0; maxcoin--) {			coinChangeL(coins, amount - maxcoin * coins[index], index - 1, cnt + maxcoin);		}	}}

转载地址：http://avxwn.baihongyu.com/