算法.動态規劃.最少錢币數問題（Java，遞歸）

問題

有11,5,1 三種币值
要湊15塊錢
問題：求 錢的張數最小
           

貪婪法

1. 貪婪法：先用最大的，然後依次，最後用1塊做填補
- 如果W比任何一張币值大，且一定可以補夠，比如有1塊就可以
- 特例：
1. w沒有币值大
2. 比如：11,5,3  選11 就湊不夠15塊,也就是說  先選最大币值未必能拼夠
3. 貪婪算法 一般情況下都不是最優解， 隻有大面值可以覆寫所有小面值，這種方案才能得到最優解，比如：100,50,10,5,1就可以
           

動态規劃法

動态規劃方法
拼湊15塊錢，需要最小的錢的張數，稱為F(15)
那麼：
		F(15) = Min( F(15-11) + 1, F(15-5) + 1, F(15-1) + 1 )
			  = Min( F(4) , F(10) , F(14) ) + 1

		F(10) = Min( F(10-11) + 1, F(10-5) + 1, F(10-1) + 1)
			  = Min( F(-1) , F(5) , F(9) )+ 1
			  = Min( F(5) , F(9) )+ 1
			  = Min( 1 , F(9) )+ 1
說明：
F(4)+1 : 用了一張11塊币值，剩餘需要湊4塊的錢的張數
F(5) ： 湊跟币值一樣的錢數，當然是直接使用一張5塊的就算完事
F(10): 湊10塊 可以選：5，也可以選1塊。 這個還按照貪婪從大到小，當然還需要比對。
	- 優化點：咱看到5的下一級隻需要取5塊，2張就完事。 就沒必要：5+1+1+1+1+1 直到最後

類似問題：
1. 第n個元素的值：F(n) = F(n-2) + (n-1)
	- n=1,2為2,3
2. 導航問題：假設A-Z導航，A後兩條出口B，C
	- Min(a,z) = Min( (A-B) + Min(B,Z) ,(A-C) + Min(C,Z) )

編碼：遞歸，這類問題用遞歸 跟問題分析很對應
           

代碼(Java)

@Test
	public void test1(){
		// 有11,5,1 三種币值
		int [] currencyValues =new int[]{11,5,1};
		// 要湊15塊錢
		int w = 15; 
		// 問題：求 錢的張數最小
		Solution Solution = new Solution();
		Assert.assertEquals(3, Solution.miniNumberOfMoney(currencyValues,w));
		Assert.assertEquals(2, Solution.miniNumberOfMoney(new int[]{11,5,1},6));
		// 這種就是無解場景
		Assert.assertEquals(2, Solution.miniNumberOfMoney(new int[]{11,5,2},6));
	}
	
	/**
	 * 動态規劃方法
	 * 拼湊15塊錢，需要最小的錢的張數，稱為F(15)
	 * 那麼：
	 * 		F(15) = Min( F(15-11) + 1, F(15-5) + 1, F(15-1) + 1 )
	 * 			  = Min( F(4) , F(10) , F(14) ) + 1
	 * 
	 * 		F(10) = Min( F(10-11) + 1, F(10-5) + 1, F(10-1) + 1)
	 * 			  = Min( F(-1) , F(5) , F(9) )+ 1
	 * 			  = Min( F(5) , F(9) )+ 1
	 * 			  = Min( 1 , F(9) )+ 1
	 * 說明：
	 * F(4)+1 : 用了一張11塊币值，剩餘需要湊4塊的錢的張數
	 * F(5) ： 湊跟币值一樣的錢數，當然是直接使用一張5塊的就算完事
	 * F(10): 湊10塊 可以選：5，也可以選1塊。 這個還按照貪婪從大到小，當然還需要比對。
	 * 	- 優化點：咱看到5的下一級隻需要取5塊，2張就完事。 就沒必要：5+1+1+1+1+1 直到最後
	 * 
	 * 類似問題：
	 * 1. 第n個元素的值：F(n) = F(n-2) + (n-1)
	 * 	- n=1,2為2,3
	 * 2. 導航問題：假設A-Z導航，A後兩條出口B，C
	 * 	- Min(a,z) = Min( (A-B) + Min(B,Z) ,(A-C) + Min(C,Z) )
	 * 
	 * 編碼：遞歸，這類問題用遞歸 跟問題分析很對應
	 */
	class Solution {
		public int miniNumberOfMoney(int[] moneys,int w) {
			int miniNum = Integer.MAX_VALUE;
			int tempMiniNum = 0;
			for(int i = 0 ; i < moneys.length ; i++){
				if(moneys[i] > w){
					// 拼湊的錢直接比目前币值小，比如拼湊99塊，100面值就直接過了。
					continue;
				}else if(moneys[i] == w){
					// 拼湊的錢 跟 比目前币值相等，那麼最新少的就是一張
					tempMiniNum = 1;
				}else if(moneys[i] < w){
					tempMiniNum = miniNumberOfMoney(moneys,w - moneys[i]) + 1;
				}
				
				// 如果這種币值的錢張數 比較少就記錄
				if(tempMiniNum < miniNum){
					miniNum = tempMiniNum;
				}
			}
			
			return miniNum;
		}
	}
           

end