322. Coin Change

給定一個表示不同面額硬幣的整數數組coins和一個amount表示總金額的整數，回傳組成amount所需最少硬幣數量，若不存在組合方法則回傳-1。

https://leetcode.com/problems/coin-change/

範例
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

也是使用Dp來解決，和這題相同的解法。

使用範例來思考，從後往前推算，將11的最小組成硬幣數寫為F(11)，在組出11的前一步可能為 10、9 或 6，而我們是要求最小值，其實就是Min(F(10),F(9),F(6)) + 1 。

而F(10) = Min(F(9),F(8),F(5)) + 1。

如上圖，只要一直往前追溯，直到遇到最小的F(1)、F(2)、F(5)，就能得出答案。

若遇到數字小於幣值大小，如F(2)紅色箭頭則略過比較。因此F(2)的組成方式只有

Min(F(1),F(-1),F(-4)) + 1。

雖然範例沒有，但有時會遇到所有幣值都大於組合的狀況，這時直接給-1即可，後續在比較最小值時將排除-1。

寫成程式碼如下，但效能實際跑過後不佳，應該是判斷式太多了，有機會再改良﹍

	public int coinChange(int[] coins, int amount) {

		// 若 amount=0 則不需要任何硬幣
		if (amount == 0) {
			return 0;
		}

		int[] dp = new int[amount];
		int ans = coinChange(coins, amount, dp);

		return ans;
	}

	public int coinChange(int[] coins, int amount, int[] dp) {

		int ans = Integer.MAX_VALUE;
		for (int coin : coins) {
			if (amount < coin) {
				// 硬幣大於組成數字
				dp[amount - 1] = -1;
				continue;
			} else if (amount == coin) {
				// 硬幣等於組成數字
				dp[amount - 1] = 1;
				return 1;
			}
			int tmp;

			// 比較大小，若以計算過則直接從dp[]取出，否則呼叫遞迴來計算
			if (dp[amount - coin - 1] != 0) {
				tmp = dp[amount - coin - 1];
			} else {
				tmp = coinChange(coins, amount - coin, dp);
			}
			if (tmp == -1) {
				continue;
			}
			ans = Math.min(tmp, ans);

		}

		if (ans == Integer.MAX_VALUE) {
			// 出現這種狀況表示每種硬幣都大於組成數字
			ans = -1;
		} else {
			// 存在前次的組成方法，將其+1作為本次的最小值
			ans = ans + 1;
		}
		dp[amount - 1] = ans;

		return ans;
	}