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

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

　　實例講解

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

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

　　func Fib（） -》 Int {

　　var prev = 0

　　var curr = 1

　　for _ in 1 。。《 100 {

　　var temp = curr

　　curr = prev + curr

　　prev = temp

　　}

　　return curr

　　}

　　用動態規劃怎么寫呢？首先要明白動態規劃有以下幾個專有名詞：

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

　　2. 狀態轉移方程，即第n個問題的解和之前的 n - m 個問題解的關系。在這道題目里，我們已經有了狀態轉移方程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）正是我們所謂的初始狀態，即 F（2） = 1，F（1） =1。所以代碼如下：

　　func Fib（n： Int） -》 Int {

　　// 定義初始狀態

　　guard n 》 0 else {

　　return 0

　　}

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

　　return 1

　　}

　　// 調用狀態轉移方程

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

　　}

　　print（Fib（100））