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

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

　　實例講解

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

　　這道題目乍一看是一個數(shù)學(xué)題，那么要求第100個數(shù)字，很簡單，一個個數(shù)字算下去就是了。假設(shè)F（n）表示第n個斐波拉契數(shù)列的數(shù)字，那么我們易得公式F（n） = F（n - 1） + F（n - 2），n 》= 2，下面就是體力活。當然這道題轉(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

　　}

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

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

　　2. 狀態(tài)轉(zhuǎn)移方程，即第n個問題的解和之前的 n - m 個問題解的關(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））