參考博客https://cloud.tencent.com/developer/article/1453737
學(xué)習(xí)動(dòng)態(tài)規(guī)劃的筆記蔗坯，博客中的兩個(gè)小demo都用python實(shí)現(xiàn)了一次冗尤。
首先從斐波那契數(shù)列入手，斐波那契數(shù)列可以看做一個(gè)簡(jiǎn)單的動(dòng)態(tài)規(guī)劃哗脖。求f(n) = f(n-1) + f(n-2),這個(gè)大學(xué)都學(xué)過祈餐，用一個(gè)遞歸就可以求出來了擂啥，而且其實(shí)也是比較直觀的。比如f(100) 就可以知道事f(99) + f(98)然后一次類推一個(gè)個(gè)算出來帆阳，但是這樣子有一個(gè)問題哺壶，就是復(fù)雜度極高，O(2**n),指數(shù)爆炸！我嘗試在python下用這個(gè)求100的斐波那契數(shù)山宾，就已經(jīng)要算很久了至扰。于是乎就有了改進(jìn)，通過一個(gè)表記錄子問題的答案资锰。這樣子 一下子復(fù)雜度就下降成線性的O(n)敢课，在python代碼下100，甚至1000很快就算出來（Ps.在python種遞歸調(diào)用超過1000是不被允許的绷杜，需要修改配置參數(shù)翎猛。而且斐波那契1000也太大了吧），最后還有一點(diǎn)優(yōu)化空間接剩，就是上面的思路都是從上往下算，還可以從下網(wǎng)上算萨咳，這就是動(dòng)態(tài)規(guī)劃的思路了懊缺。可以看到斐波那契數(shù)列之和他前兩個(gè)數(shù)有關(guān)培他，那就可以從f（1）開始計(jì)算鹃两，算道f(100)，復(fù)雜度為O(1)舀凛。
有了上面例子的鋪墊俊扳，開始看硬幣問題。類似01背包猛遍，需要用盡可能少的硬幣數(shù)目拼湊初目標(biāo)金額馋记。
終于把硬幣問題的三種解法（遞歸/備忘錄/dp）看完了，說實(shí)話遞歸是最容易繞進(jìn)去的懊烤，由于實(shí)在存在太多的分支導(dǎo)致就算想要一步一步的按照邏輯走一遍馬上就會(huì)亂掉梯醒。而當(dāng)最后寫出dp的解法后就會(huì)發(fā)現(xiàn)是如此的簡(jiǎn)單優(yōu)雅，代碼貼上去腌紧。這里雖然現(xiàn)在理解了茸习，但是肯定不過一段時(shí)間遺忘的，或者換一個(gè)形式出現(xiàn)又不知道怎么解決了壁肋，總之還需多看啊号胚。只要理解了動(dòng)態(tài)規(guī)劃的中心思想，代碼是如此的簡(jiǎn)單優(yōu)雅浸遗。
fib_result = {}
coin_result_dict = {}
import sys
sys.setrecursionlimit(9000000) #這里設(shè)置大一些
'''
遞歸暴力求解猫胁，O(n**2)效率低下
python對(duì)遞歸的調(diào)用次數(shù)有限制，超過1000次就會(huì)報(bào)錯(cuò)跛锌，可以修改參數(shù)配置
import sys
sys.setrecursionlimit(9000000) #這里設(shè)置大一些
'''
def fib(n):
if n == 1 or n == 2:
return 1
return fib(n-1) + fib(n-2)
'''
備忘錄方法杜漠，通過記錄子問題的解，減少計(jì)算次數(shù)
復(fù)雜度O(n)
'''
def fib_helper(n):
if n == 1 or n == 2:
return 1
return result(n-1) + result(n-2)
def result(n):
if not n in fib_result:
fib_result[n] = fib_helper(n)
return fib_result[n]
'''
動(dòng)態(tài)規(guī)劃的思路，自下而上的求解
'''
def fib_dp(n):
dp_map = {1:1,2:1}
for i in range(3, n+1):
dp_map[i] = dp_map[i - 1] + dp_map[i - 2]
return dp_map[n]
'''
進(jìn)一步優(yōu)化驾茴，只保存前兩個(gè)信息盼樟，復(fù)雜度為O(1)
'''
def fib_dp2(n):
if n < 2:
return n
prev = 0
curr = 1
for i in range(1, n):
sum = prev + curr
prev = curr
curr = sum
return curr
###################################################################################
'''
上面是斐波那契數(shù)列
下面的例子是硬幣組合
即又c種不同面額的貨幣，c1,c2,c3...ck 需要組合成n元锈至，最少需要多少個(gè)硬幣
遞歸問題的關(guān)鍵是狀態(tài)轉(zhuǎn)移方程晨缴，在這個(gè)問題中硬幣數(shù)目f(n) = 1 + min{f(n - ci)|i 屬于 [i,k]}
'''
'''
先用遞歸的方法求解
'''
def coin_cur(c,n):
ans = sys.maxsize
if n == 0:
return 0
for c_single in c:
if c_single > n:
continue
rest_amount = coin_cur(c, n - c_single)
if rest_amount == -1:
continue
print(c_single) # 輸出一個(gè)硬幣隊(duì)列，結(jié)合函數(shù)輸出峡捡，例如3击碗，就是最后三個(gè)數(shù)組即是所需的硬幣組合
ans = min(ans, rest_amount + 1) # 注意上面的狀態(tài)轉(zhuǎn)移方程，此處就是對(duì)比ci1情況下和ci2情況下那種需要用到的硬幣少
return -1 if ans == sys.maxsize else ans
'''
帶備忘錄的方法
'''
def coin_cur_help(c, n):
ans = sys.maxsize
if n == 0:
return 0
for c_single in c:
if c_single > n:
continue
rest_amount = coin_result(c, n - c_single)
if rest_amount == -1:
continue
else:
#print(c_single)
ans = min(ans,rest_amount + 1)
return -1 if ans == sys.maxsize else ans
def coin_result(c, n):
if not n in coin_result_dict:
coin_result_dict[n] = coin_cur_help(c, n)
return coin_result_dict[n]
'''
動(dòng)態(tài)規(guī)劃
'''
def coin_dp(c, n):
dp_map = {0:0}
for i in range(1, n+1):
dp_map[i] = sys.maxsize
for k in dp_map:
for c_single in c:
if k < c_single:
continue
else:
dp_map[k] = min(dp_map[k], 1+dp_map[k - c_single])
return dp_map[n] if dp_map[n] != sys.maxsize else -1
if __name__ == '__main__':
c = [5,10]
n = 7
print(coin_dp(c, n))
