這里簡要講一下尤仍，遇到動態(tài)規(guī)劃問題應該如何快速找到出發(fā)點
我們以例子來說明：
# 題目：給你 k 種面值的硬幣箫津，面值分別為 c1, c2 ... ck，再給一個總金額 n宰啦，
#問你最少需要幾枚硬幣湊出這個金額苏遥，如果不可能湊出，則回答 -1 赡模。
#比如說田炭，k = 3，面值分別為 1漓柑，2教硫，5，總金額 n = 11辆布，那么最少需要 3 枚硬幣瞬矩，即 11 = 5 + 5 + 1 。下面走流程锋玲。
首先景用，我們要先找到 f(n)，這是最終問題,?在這里惭蹂，即是金額為n時伞插，f(n)代表最少需要的硬幣數(shù)
接著，要找到 f(n)與子項的關(guān)系盾碗！?固現(xiàn)在開始就是要將f(n)進行分解媚污，一般是思維，是想到與 f(n-1)的關(guān)系廷雅！?然而這里并不是杠步，因為f(n-1)代表的是當金額為n-1時，需要的最少硬幣數(shù)榜轿。? 真實的聯(lián)系是幽歼，最后一枚幣時，前面已經(jīng)到達了最小值谬盐。
# f(n) = 1 +Min{f(n-ci)|i->[0,k] }? (n>0)?
然而動態(tài)規(guī)劃還有一個點甸私，叫自下而上！?也就是說飞傀，我要先算 f(n),就得先算出 f(1),f(2).....
對應該題皇型，我們應該要先算出?當金額為1時诬烹，最少多少個幣，金額為2時弃鸦，最小多少個幣...最后才有金額為n時绞吁，金額多少幣！
固多數(shù)情況下唬格，我們都需要用一個map來存這些歷史數(shù)據(jù)家破，key就是金額，value就是次數(shù)购岗！?只有這里存儲過后汰聋，才能很方便的使用上面發(fā)現(xiàn)的公式：?f(n) = 1 +Min{f(n-ci)|i->[0,k] }? (n>0)
好了，最后總結(jié)動態(tài)規(guī)劃的下手倆點：
1喊积、找到子項聯(lián)系烹困，可能是 f(n)與f(n-1)?的關(guān)系，也可能是 f(n) = 1+極值? 的關(guān)系
2乾吻、找到自下而上的關(guān)系髓梅！?即是要求出 f(1),f(2)...最終求得f(n)
3、第2條與第1條聯(lián)用一般就是倆個FOR循環(huán)
