這里簡(jiǎn)要講一下，遇到動(dòng)態(tài)規(guī)劃問(wèn)題應(yīng)該如何快速找到出發(fā)點(diǎn)

我們以例子來(lái)說(shuō)明：

# 題目：給你 k 種面值的硬幣，面值分別為 c1, c2 ... ck，再給一個(gè)總金額 n，

#問(wèn)你最少需要幾枚硬幣湊出這個(gè)金額，如果不可能湊出，則回答 -1 。

#比如說(shuō)，k = 3，面值分別為 1，2，5，總金額 n = 11，那么最少需要 3 枚硬幣，即 11 = 5 + 5 + 1 。下面走流程。

首先，我們要先找到 f(n)，這是最終問(wèn)題,?在這里，即是金額為n時(shí)，f(n)代表最少需要的硬幣數(shù)

接著，要找到 f(n)與子項(xiàng)的關(guān)系！?固現(xiàn)在開(kāi)始就是要將f(n)進(jìn)行分解，一般是思維，是想到與 f(n-1)的關(guān)系！?然而這里并不是，因?yàn)閒(n-1)代表的是當(dāng)金額為n-1時(shí)，需要的最少硬幣數(shù)。? 真實(shí)的聯(lián)系是，最后一枚幣時(shí)，前面已經(jīng)到達(dá)了最小值。

# f(n) = 1 +Min{f(n-ci)|i->[0,k] }? (n>0)?

然而動(dòng)態(tài)規(guī)劃還有一個(gè)點(diǎn)，叫自下而上！?也就是說(shuō)，我要先算 f(n),就得先算出 f(1),f(2).....

對(duì)應(yīng)該題，我們應(yīng)該要先算出?當(dāng)金額為1時(shí)，最少多少個(gè)幣，金額為2時(shí)，最小多少個(gè)幣...最后才有金額為n時(shí)，金額多少幣！

固多數(shù)情況下，我們都需要用一個(gè)map來(lái)存這些歷史數(shù)據(jù)，key就是金額，value就是次數(shù)！?只有這里存儲(chǔ)過(guò)后，才能很方便的使用上面發(fā)現(xiàn)的公式：?f(n) = 1 +Min{f(n-ci)|i->[0,k] }? (n>0)

好了，最后總結(jié)動(dòng)態(tài)規(guī)劃的下手倆點(diǎn)：

1、找到子項(xiàng)聯(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)用一般就是倆個(gè)FOR循環(huán)