零钱兑换（力扣）_零钱兑换 算法

零钱兑换（力扣）

分析：

原问题：凑成总金额S所需的最少硬币个数；
子问题：可凑成目标金额x（x<=S）所需的最少的硬币个数；

// c 表示硬币价值
状态转移方程：f(x)=min{ f(x-c1), f(x-c2), … , f(x-c2) }+1
// +1表示有一枚c值的硬币
注意：当 x-ci < 0，表示，硬币价值比要凑的目标金额还要大，排除不选。
当 x-ci = 0，即目标金额为0，不需要硬币。
题目说，没有任何一种硬币组合，S就返回-1，因此最好我们需要判断一下f(S)是否为正无穷。

从前开始，避免重复计算。

java代码实现

	public int coinChange(int[] coins, int amount) {
		int max = amount+1;
		int[] dp = new int[amount+1];
		Arrays.fill(dp, max);	//快速初始化数组	
		dp[0] = 0;	//表示 coins的第一个元素 ，需要一枚硬币组成，就是自己。
		
		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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

另一个思路，其实看到题第一个想到的是 贪心

1. 想要总硬币数最少，肯定是优先用大面值硬币，所以对 coins 按从大到小排序
2. 先丢大硬币，再丢会超过总额时，就可以递归下一层丢的是稍小面值的硬币

但没写出来，测试用例后，发现只用贪心好像不是那么简单，写不出来。
现实生活中，找零钱问题，可以使用贪心算法，因为每张钱都是由对应的倍数关系。