前情參見：http://www.itdecent.cn/p/558294dae12e
我叫歐木峰，是一名心理醫(yī)生。
國(guó)外留學(xué)歸來，我創(chuàng)辦了辛境診所。關(guān)小破是我的第一個(gè)患者，他是我高中同學(xué)子瑾的男朋友，患有幻聽癥。歸國(guó)之前子瑾曾和我說起過她的男朋友，并尋求我的幫助。關(guān)小破，一個(gè)典型的理科IT男，天生有種不可理喻的執(zhí)拗勁，對(duì)待任何事情都很專一。子瑾說她心底里很喜歡這種性格，她說可能是公司的加班壓力大，生活節(jié)奏快才讓關(guān)患上的幻聽癥，但是我并不這么認(rèn)為，這件事也成為我回國(guó)辦心理診所的考量之一。
回國(guó)后，我和子瑾聯(lián)系了幾次，也特意叮囑過她，不能讓關(guān)知道我和她的同學(xué)關(guān)系。針對(duì)關(guān)小破的情況，我和子瑾制定了三個(gè)方案，最終選定哪一個(gè)，只有我見到本人才可以決定。
那天下午2點(diǎn)，我的診所走進(jìn)來一位男士，牛仔褲、T恤衫配上運(yùn)動(dòng)鞋，戴著大大的眼鏡，長(zhǎng)得很清秀，很陽光。
“我是關(guān)小坡，是瑾兒，是林子瑾介紹我來的”
“你好，我是歐木峰，這邊坐，可樂、果汁還是咖啡”
“咖啡吧，這會(huì)有點(diǎn)困”
“你說一下你的大致情況吧”
“那我就和你說下今天上午的事情吧”
聽完小破的自述，他的病因沒有出乎我的意料。他是因?yàn)樽晕乙庾R(shí)太過于強(qiáng)大，封閉了感官系統(tǒng)的外界連接，下意識(shí)的把自己的內(nèi)心感受幻想為從外界得到的信息，從而產(chǎn)生幻聽的感覺。簡(jiǎn)而言之就是腦洞太大。這種病如果任由其發(fā)展，就會(huì)完全陷入自己的意識(shí)里，不能脫離。
“你愛你女朋友嗎”
“當(dāng)然，如果沒有他，這些日子我真不知道怎么度過”
“那你幻聽過你女朋友的話嗎”
“那倒沒有，好像真沒有過”
這更加驗(yàn)證了我的判斷，因?yàn)樗軔圩予?，在接收來自子瑾的信息時(shí)，他強(qiáng)大的自我意識(shí)根本無法封閉住這連接，看來他真的很愛子瑾，也很愛推理。
“不好意思，我先出去一下打個(gè)電話，你在這等我一下啊，我這里有本數(shù)學(xué)謎題，你感興趣可以看一下”
“子瑾，按方案三吧！我知道對(duì)你來說這個(gè)很難，但是這樣是最好的。因?yàn)樗麖膩頉]有幻聽過你說的話”
“還來點(diǎn)咖啡嗎”
“不用了，我看見數(shù)學(xué)題就來精神”
“我也很喜歡這些數(shù)學(xué)謎題，總想找到結(jié)果，前幾天我看見一個(gè)有趣的問題，你聽過換零錢嗎，就是將面值100元的錢，換成面值1,2,5,10,20的錢，有多少種換法”
++++++一本正經(jīng)的分割線+++++++
把100元兌換成1元，2元，5元，10元，20元，50元的零錢，共有多少種不同換法。
暴力依然可以解決問題，但是不優(yōu)雅。因?yàn)樾枰鄬觙or循環(huán)，并且移植性較差，對(duì)數(shù)值不同的問題需要更改程序。本文依然采用遞歸和動(dòng)態(tài)規(guī)劃的方法解決問題。
1，拆解子問題
下面以5元換成1,2,3元的零錢為例。T[(change),target]表示用零錢系列change組成target的所有方法。見下圖：
其中T1可以看做用1和2元、不用3元組成5元的方法數(shù)；T2可以看做用1和2元、用1個(gè)3元組成5元的方法數(shù)；T6可看做用1元，用1個(gè)2元、不用3元組成3元的方法數(shù)；T9可看做用1元，用1個(gè)2元、1個(gè)3元組成0元的方法數(shù)。
狀態(tài)轉(zhuǎn)移表達(dá)式：
邊界條件：
M-nd不得小于0，并且M-nd等于0時(shí)，表達(dá)式結(jié)果為1。如果表達(dá)式為T[(a),c],只有c除以a為整數(shù)，此表達(dá)式為1，否則為0。例如T[(2),5]=0,T[(2),6]=1。
1，遞歸的Python3實(shí)現(xiàn)
#根據(jù)邊界條件，判斷結(jié)果
def Solve(exlist,target):
#判斷問題解
if target==0:
return 1
else:
if len(exlist)==1 and target%exlist[0]==0:
return 1
else:
return 0
#遞歸的方式，先將問題拆解子問題 ，然后在求解
def Dismantle(exlist):
if len(exlist[0][0])>1:
fu=[]
for ie in exlist:
for ji in range(int(ie[1]/ie[0][-1])+1):
fu.append([ie[0][0:-1],ie[1]-ji*ie[0][-1]])
return Dismantle(fu)
else:
return exlist
#計(jì)算結(jié)果
def Recursion(exlist,target):
structer=[[exlist,target]]
count=0
for jj in Dismantle(structer):#所有子問題的集合
if Solve(jj[0],jj[1])==1:#計(jì)算每一個(gè)子問題的結(jié)果
count+=Solve(jj[0],jj[1])
return count
print(Recursion([1,2,5,10,20,50],100))
結(jié)果：4562
2，動(dòng)態(tài)規(guī)劃的Python3實(shí)現(xiàn)
#動(dòng)態(tài)規(guī)劃
def DP_Com(exlist,num):
an=[1]+[0]*num
for i in exlist :
for j in range(i,num+1):
an[j]+=an[j-i]
return an[num]
print(Recursion([1,2,5,10,20,50],100))
結(jié)果：4562
++++++突如其來的分割線+++++++
關(guān)小坡這時(shí)給我說出了解題思路，但是事情并沒有結(jié)束，他的眼睛直勾勾的盯著我，但是他根本沒在看我。接下來的事情更加驗(yàn)證了我的推斷。
++++++不能自已的分割線+++++++
有面值為1元、3元和5元的錢幣若干張，如何用最少的錢幣湊夠11元，并列出組合方法。
子問題的狀態(tài)轉(zhuǎn)移表達(dá)式。
以下圖為例：
動(dòng)態(tài)規(guī)劃的Python3實(shí)現(xiàn)
#記錄
def DP_Min(exlist,target):
fan=[0]+[target]*target
record=['']*(target+1)
#存儲(chǔ)最后一位
lic=[]
for i in exlist:
for j in range(i,target+1):
if fan[j-i]!=target:#如果等于target，說明之前沒有數(shù)的結(jié)合可以達(dá)到這個(gè)數(shù)
fan[j]=min(fan[j-i]+1,fan[j])
#記錄
if fan[j-i]+1<=fan[j]:
record[j]=record[j-i]+'%d*'%i
else:
record[j]=record[j]
if record[-1]!='':
lic.append(record[-1])
if len(lic)==0:
return '無解'
else:
return lic,fan[target]
#處理字符串
def Handle(exstr,num):
for i in set(exstr):
hu=i.split('*')
hu=list(filter(lambda x:x,hu))#去除掉split留下的空格
if len(hu)==num:
shuoming=''
for j in set(hu):
shuoming+='%s個(gè)%s '%(hu.count(j),j)
print(shuoming)
return 'Done'
ggg=DP_Min([1,3,5],11)
print(Handle(ggg[0],ggg[1]))
結(jié)果：最少為3。組合方法：2個(gè)5 1個(gè)1
++++++一劑猛藥的分割線+++++++
未完待續(xù)
