這里簡要講一下，遇到動態(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)與子項的關系！?固現(xiàn)在開始就是要將f(n)進行分解，一般是思維，是想到與 f(n-1)的關系！?然而這里并不是，因為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)

好了，最后總結動態(tài)規(guī)劃的下手倆點：

1、找到子項聯(lián)系，可能是 f(n)與f(n-1)?的關系，也可能是 f(n) = 1+極值? 的關系

2、找到自下而上的關系！?即是要求出 f(1),f(2)...最終求得f(n)

3、第2條與第1條聯(lián)用一般就是倆個FOR循環(huán)