題外話：
好久沒寫博客了逛绵，主要覺得自己寫的不怎么樣，肚子沒墨水了犯助。今天又出來榨干肚子里的最后一滴墨水癣漆。
進(jìn)入正題：
前面寫過兩篇動態(tài)規(guī)劃的題目，今天又遇到動態(tài)規(guī)劃了剂买，想到了一個更容易理解的方法，我們用湊硬幣這道題目來加深理解癌蓖。網(wǎng)絡(luò)上這個題目已經(jīng)被寫爛了瞬哼，大多數(shù)文章都是復(fù)制粘貼的。本文原創(chuàng)租副。開始講解之前讀者需要了解遞歸坐慰。本文從遞歸解法講起直到推出動態(tài)規(guī)劃方法。
問題描述：
（湊硬幣問題）給你 k 種面值的硬幣用僧，面值分別為 c1, c2 ... ck 结胀，每種硬幣的數(shù)量無限赞咙，
再給一個總金額 amount ，問你最少需要幾枚硬幣湊出這個金額糟港，如果不可能湊出攀操，算法返回-1
這里我們k = 3 , c1 = 1、c2 = 3秸抚、c3 = 5.
1. 遞歸解法：
形象的理解遞歸：
比如f是一個八卦的人速和，有一天a和b談戀愛了，只告訴了c剥汤。 f想知道a和b的關(guān)系颠放， 就去問e， e說他自己不知道可以幫忙去問d吭敢，d說他也不知道可以幫忙去問c（遞歸調(diào)用過程）碰凶，c呢就告訴了d，d又告訴了e鹿驼，e告訴了f（回溯過程痒留，回溯過程可以看作答案一步步傳到f耳朵里的過程）。
用遞歸的思想來思考該問題大致如下：
我們知道amount=0和amount<0基本情況（c知道a和b的關(guān)系）蠢沿，求amount=11的答案（f想知道a和b的關(guān)系）伸头，ans(11)=ans（11-5）+1 or ans(11)= ans(11-3)+1 or ans(11)= ans(11-1)+1 （f去問了他認(rèn)識的人e。如果f認(rèn)識d或者直接認(rèn)識c他可以更快的知道答案）舷蟀。遞歸的回溯過程程序會自動完成恤磷。
def colCoins_rec(coins, amount):
"""
遞歸解法
:param coins: 硬幣面值
:param amount: 總金額
:return: 湊齊總金額的最少硬幣數(shù)量
"""
# 基本情況（c知道的情況）
if amount == 0:
return 0
if amount < 0:
return -1
res = float("inf")
# 有三種面值的硬幣可以選擇（f認(rèn)識的人，因?yàn)閒只認(rèn)識e所以只有一個選擇）
for coin in coins:
#選擇（f選擇問誰野宜，交給誰來獲取答案）
subproblem = colCoins_rec(coins, amount-coin)
# 子問題無解扫步，（f問到了錯誤地人g，g是個孤兒誰都不認(rèn)識匈子，走到了死胡同河胎，f要問下一個人）
if subproblem < 0: continue
# 選擇最優(yōu)的答案（如果f認(rèn)識c，那么他很快可以獲取答案虎敦，就可以選擇這條信息鏈）
res = min(res, 1+colCoins_rec(coins, amount-coin))
return res
遞歸方法存在什么問題呢游岳？很明顯的一個是使用了函數(shù)調(diào)用棧，棧在計算機(jī)中是一個相對很有限的資源其徙。還有一個是存在重疊子問題胚迫，導(dǎo)致了時間復(fù)雜度大大增加。LeetCode上這個方法一般是無法通過的唾那。重疊子問題是什么呢访锻？
h 存在直接連線的表示互相認(rèn)識
/ \ 如果h想從c那里獲得c知道的答案那么他要問認(rèn)識的f，g同樣
f g f，g要問他們認(rèn)識的人期犬。
/ \ / \ 觀察發(fā)現(xiàn)f河哑，e，g被問了多次龟虎！這是導(dǎo)致算法復(fù)雜度高的主要原因
g e e f
/ \ ........
e f
/ \
c d
如何解決上述存在的重疊子問題呢璃谨？答案是使用備忘錄方法。
2備忘錄遞歸方法
備忘錄方法是這些人共用一個列表的遣总，如果誰已經(jīng)知道答案就填在列表對應(yīng)的元素里里睬罗，每個人在問之前先訪問列表，如果得到大難就不用再繼續(xù)問下去了旭斥，避免重復(fù)的被問容达。
mem = [-1]*15
def colCoins_rec_mem(coins, amount, mem):
"""
在遞歸的解法的基礎(chǔ)上加上備忘錄解決重疊子問題。
:param coins: 硬幣面值
:param amount: 總金額
:param mem: 備忘錄
:return: 最少硬幣數(shù)量
"""
# 基本情況（c知道的答案）
if amount < 0:
return -1
if amount == 0:
return 0
# 查看備忘錄垂券，看看是否計算過（是否被問過）
if mem[amount] != -1:
return mem[amount]
# 選擇（詢問的過程）
res = float("inf")
for coin in coins:
subproblem = colCoins_rec_mem(coins, amount-coin, mem)
if subproblem < 0: continue
res = min(res, 1+colCoins_rec_mem(coins, amount-coin, mem))
# 得到答案后寫進(jìn)備忘錄
mem[amount] = res
return res
我們可以看到基于備忘錄的遞歸算法花盐，會在計算（詢問）前去查看備忘錄，避免重復(fù)計算菇爪。而且代碼與純遞歸方法也非常的相似算芯。只多了查看備忘錄的過程和獲得答案后寫進(jìn)備忘錄的操作。這個備忘錄解決了重疊子問題凳宙，實(shí)際上他還是遞歸方法熙揍。我們可以看到其實(shí)備忘錄記錄的就是子問題和原問題的答案，遞歸方法是自頂向下的以“詢問”的方法求得答案氏涩，那么可不可以讓c主動的向他認(rèn)識的人擴(kuò)散答案直到讓f知道答案届囚。這個自底向上的“傳播”就是動態(tài)規(guī)劃！（好煩c這種人啊是尖，就像我很煩動態(tài)規(guī)劃題目）話不多說看代碼
def colCoins_mem(coins, amount):
"""
自底向上遞推出答案
:param coins: 硬幣面值
:param amount: 總金額
:return:
"""
# 構(gòu)造一個備忘錄
mem = [0]*(amount+1) # mem[i]表示湊出金額i需要的最少硬幣的數(shù)量
# 基本情況（這句代碼可以不要）
mem[0] = 0
# 開始推導(dǎo)（c開始傳播八卦了）
for i in range(1, amount+1):
# 從c開始向他認(rèn)識的人傳播消息
for coin in coins:
res = i - coin
if res >= 0:
mem[i] = mem[res] + 1
else:
continue
return mem[amount]
總結(jié)：
我們看看動態(tài)規(guī)劃的要素就是：1意系、基本情況（知道答案的那個人）2、明確mem里面存儲的是什么我們也可以稱作狀態(tài)饺汹。3蛔添、選擇（每個狀態(tài)有多少轉(zhuǎn)移方方式）4、明確狀態(tài)轉(zhuǎn)移的細(xì)節(jié)（狀態(tài)轉(zhuǎn)移方程）兜辞。該文章一氣呵成有什么不懂的留言迎瞧，有空改一下。動態(tài)規(guī)劃就到這里了弦疮。
