昨天的Memo版本，是從上而下的，也就是我們從N開始，一路計算N-1，N-2．．．一直到1的過程．

那我們轉換個思路，如果我們是從1，2，3．．．一路算到N呢．

因為我們一開始拿到的初始狀態就是f(0)=0 ，f(1) = 1．這樣的計算會簡單許多．

以下是範例程式碼

fun fibonacciWithDP(n: Int): Int {
    return when(n){
        0 -> {0}
        1, 2 -> {1}
        else -> {
            val dp = IntArray(n+1)
            dp[0] = 0
            dp[1] = 1
            dp[2] = 1
            for(i in 3..n){//直接從初始狀態往最終狀態計算
                dp[i] = dp[i-1]+dp[i-2]
            }
            dp[n]
        }
    }
}

如何，表現起來很簡單吧，看起來很接近我們一開始的暴力計算，但是實際執行上的時間可是天差地別，其中的差距就在於，DP的解法同樣也只要把每個問題計算一次，與Memo版本相同，而暴力計算同樣的子問題就會算很多次

現在我們回到一開始題目的定義

F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*）

這個就是動態規劃的動態轉移方程．而以上幾種的解法，只是動態轉移方程的各種描述方法．

而一開始的這個動態轉移方程，便是直接代表暴力解法．

有些題目不會像這個範例一樣，直接給出轉移方程，而是透過一些描述．來讓人較難寫出暴力解法．

整個動態規劃問題最困難的就是在此，寫出暴力解法的動態方程，之後只要帶入Memo版本或是DP Table版本來進行最佳化，但由於這個第一步就是最困難的地方，有許多人認為動態規劃難度很高，但只要撐過去變海闊天空．

最後，還有一個可以優化的地方，回去看看上面的程式碼，是不是新的狀態，只和前面兩個狀態值有關係，所以其實我們可以不需要把陣列設定的這麼大，而只要可以存放前兩個狀態即可．這樣可以把使用的空間減少，空間複雜度變為O(1)

fun fibonacciWithDPCompress(n: Int): Int {
    return when(n){
        0 -> {0}
        1, 2 -> {1}
        else -> {
            var prevValue= 1 //只保留前面兩個狀態
            var currentValue= 1//只保留前面兩個狀態
            for(i in 3..n){
                val sum = prevValue+ currentValue
                prevValue = currentValue
                currentValue = sum
            }
            currentValue
        }
    }
}

這也是常用的技巧之一，狀態壓縮，如果發現狀態轉移其實只需要DP Table的一部分，有些部分再也用不到，那就可以來壓縮使用的空間．最常見的情況就是把一個二維陣列壓縮到一維陣列．

而動態規劃的另一個重要特性，最佳子結構，在費波那契數列的例子中沒有體現，因為費波那契數列不涉及求極值的動作，所以在嚴格意義上來說不算是一題完整的動態規劃問題．這個例子主要是描述重疊子問題的消除方法，明天我們會利用湊零錢問題來看看最佳子結構的特性．