今天要講的動(dòng)態(tài)規(guī)劃，其面對(duì)的問(wèn)題通常是無(wú)法一蹴而就，需要把復(fù)雜的問(wèn)題分解成簡(jiǎn)單具體的小問(wèn)題，然后通過(guò)求解簡(jiǎn)單問(wèn)題，去推出復(fù)雜問(wèn)題的最終解。

　　形象的理解就是為了推倒一系列紙牌中的第100張紙牌，那么我們就要先推倒第1張，再依靠多米諾骨牌效應(yīng)，去推倒第100張。

　　實(shí)例講解

　　斐波拉契數(shù)列是這樣一個(gè)數(shù)列：1， 1， 2， 3， 5， 8， 。。. 除了第一個(gè)和第二個(gè)數(shù)字為1以外，其他數(shù)字都為之前兩個(gè)數(shù)字之和?，F(xiàn)在要求第100個(gè)數(shù)字是多少。

　　這道題目乍一看是一個(gè)數(shù)學(xué)題，那么要求第100個(gè)數(shù)字，很簡(jiǎn)單，一個(gè)個(gè)數(shù)字算下去就是了。假設(shè)F（n）表示第n個(gè)斐波拉契數(shù)列的數(shù)字，那么我們易得公式F（n） = F（n - 1） + F（n - 2），n 》= 2，下面就是體力活。當(dāng)然這道題轉(zhuǎn)化成代碼也不是很難，最粗暴的解法如下：

　　func Fib（） -》 Int {

　　var prev = 0

　　var curr = 1

　　for _ in 1 。。《 100 {

　　var temp = curr

　　curr = prev + curr

　　prev = temp

　　}

　　return curr

　　}

　　用動(dòng)態(tài)規(guī)劃怎么寫(xiě)呢？首先要明白動(dòng)態(tài)規(guī)劃有以下幾個(gè)專有名詞：

　　1. 初始狀態(tài)，即此問(wèn)題的最簡(jiǎn)單子問(wèn)題的解。在斐波拉契數(shù)列里，最簡(jiǎn)單的問(wèn)題是，一開(kāi)始給定的第一個(gè)數(shù)和第二個(gè)數(shù)是幾？自然我們可以得出是1

　　2. 狀態(tài)轉(zhuǎn)移方程，即第n個(gè)問(wèn)題的解和之前的 n - m 個(gè)問(wèn)題解的關(guān)系。在這道題目里，我們已經(jīng)有了狀態(tài)轉(zhuǎn)移方程F（n） = F（n - 1） + F（n - 2）

　　所以這題要求F（100），那我們只要知道F（99）和F（98）就行了；想知道F（99），我們只要知道F（98）和F（97）就行了；想要知道F（98），我們需要知道F（97）和F（96）。。。，以此類推，我們最后只要知道F（2）和F（1）的值，就可以推出F（100）。而F（2）和F（1）正是我們所謂的初始狀態(tài)，即 F（2） = 1，F(xiàn)（1） =1。所以代碼如下：

　　func Fib（n： Int） -》 Int {

　　// 定義初始狀態(tài)

　　guard n 》 0 else {

　　return 0

　　}

　　if n == 1 || n == 2 {

　　return 1

　　}

　　// 調(diào)用狀態(tài)轉(zhuǎn)移方程

　　return Fib（n - 1） + Fib（n - 2）

　　}

　　print（Fib（100））

相關(guān)電子資料下載

• 拿下國(guó)家級(jí)信創(chuàng)認(rèn)證！中科馭數(shù)KPU SWIFT-2200N成為國(guó)內(nèi)首款滿足金融業(yè)嚴(yán)苛要求的 163
• 中科馭數(shù)基于DPU的思威SWIFT系列智能網(wǎng)卡與統(tǒng)信軟件產(chǎn)品完成適配 176
• 如何使用Swift提高代碼質(zhì)量 126
• 積木易搭Magic Swift Plus為雕刻工藝品精雕復(fù)刻提供三維數(shù)字化解決方案 274
• 詞法分析-Antlr-1 235
• Kotlin 1.8.0發(fā)布，改進(jìn)性能和Swift的互操作性 1044
• Swift 2023：強(qiáng)調(diào)并發(fā)、泛型和C++互操作性，開(kāi)發(fā)Swift解析器 300
• 彩色套件創(chuàng)建全彩3D模型MagicSwiftPlus僅千元級(jí) 432
• Swift的使用體驗(yàn)與生態(tài)發(fā)展之路 981
• 如何加速apply函數(shù)600倍的技巧 627