參考資料 http://blog.csdn.net/baidu_28312631/article/details/47418773
http://www.360doc.com/content/13/0601/00/8076359_289597587.shtml
1. 問題：
現(xiàn)在有1,3,5元硬幣若干枚震缭，使用最少的數(shù)量湊夠11元
-
貪心算法
先選擇最大的诱渤，兩枚5元的衡载，再選擇3元的，不行，那就選擇1元的蠕搜，正好公浪，總共用了3枚硬幣。但是如果把面值改成了2亭病，3，5嘶居，那用貪心算法就永遠(yuǎn)湊不齊了罪帖。
-
動態(tài)規(guī)劃法
假設(shè)湊夠i元需要j枚硬幣，那么就有d(i)=j這樣的公式邮屁，i是小于11的
假如i=4整袁，硬幣最大值5，不能用佑吝，那就用一個3坐昙，可以用，所以可以得出d(4)=1+d(4-3),由于我們是按照i從小到大的順序算的芋忿，所以d(4-3)已經(jīng)計算出來了炸客，所以。戈钢。
| i | j |
|---|---|
| 0 | d(0)=0 * (表示湊0元需要0個硬幣) * |
| 1 | d(1)=1+d(1-1)=1+0=1 * 表示湊1元需要1個硬幣 * |
| 2 | d(2)=1+d(2-1)=1+1=2 |
| 3 | d(3)=Min(1+d(3-3),1+d(3-1))=1 |
| 4 | d(4)=Min(1+d(4-3),1+d(4-1))=2 |
| 5 | d(5)=Min(1+d(5-5),1+d(5-3),1+d(5-1))=1 |
| 6 | d(6)=Min(1+d(6-5),1+d(6-3),1+d(6-1))=2 |
| 7 | d(7)=Min(1+d(7-5),1+d(7-3),1+d(7-1))=3 |
| 8 | d(8)=Min(1+d(8-5),1+d(8-3),1+d(8-1))=2 |
| 9 | d(9)=Min(1+d(9-5),1+d(9-3),1+d(9-1))=3 |
| 10 | d(10)=Min(1+d(10-5),1+d(10-3),1+d(10-1))=2 |
| 11 | d(11)=Min(1+d(11-5),1+d(11-3),1+d(11-1))=3 |
2. 問題：
求從頂端到底端路線痹仙，經(jīng)過的點的之和最大的路徑，只能往左下殉了，右下走
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
-
遞歸法
-
普通遞歸法：從最上面一行開始开仰，下面一行它左面的和他右邊的分別加上它，求最大值薪铜，然后開始遞歸众弓，直到下一行沒有（當(dāng)前這行就是最后一行）
這樣的話就是無腦遞歸，第二行的3開始往下計算隔箍，會分別計算8谓娃、1這三個分支，從第二行的8開始往下計算蜒滩，會計算1滨达、0兩個分支，那么1這個分支就重復(fù)計算了帮掉，所以弦悉。。蟆炊。
-
改進(jìn)遞歸法：上面那種方法中稽莉，有東西重復(fù)計算了，所以我們可以把它記錄下來
這樣的話就是無腦遞歸涩搓，第二行的3開始往下計算污秆，會分別計算8劈猪、1這三個分支，從第二行的8開始往下計算良拼，會計算1战得、0兩個分支，那么1這個分支就重復(fù)計算了庸推，所以常侦。。贬媒。
-
-
動態(tài)規(guī)劃法
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
- 從最下面開始聋亡，首先記錄4 5 2 6 5
- 倒數(shù)第二行，2和最后一行的4际乘、5中求出一個最大的和坡倔，7和最后一行的5、2脖含，4和最后一行的2罪塔、6，4和最后一行的6养葵、5征堪，最后記錄下7 12 10 10
- 倒數(shù)第三行，同理港柜，最后記錄下20 13 10
- 倒數(shù)第四行请契，同理咳榜，最后記錄下23 21
- 最上面一行夏醉，同理，最后記錄下30
- 如此涌韩，得到了最后的答案畔柔。
3. 問題：
解題思路:動態(tài)規(guī)劃求解，通常把原問題分成子問題臣樱，前一個子問題解決之后靶擦，答案保存下來，供下一個子問題去使用雇毫，以上兩個問題都是遮陽解的玄捕，所以每個問題只需要解一次
