在昨天我們發現了，我們執行了很多重複的運算，下面的圖同樣的顏色就是同樣的數據．

那有沒有辦法減少重複的計算呢．這就是我們今天的重點了，Memo．

當如果Momo裡面有已經計算過的子問題，就直接拿出來，就不用重新計算．

通常Momo都是使用Array來當作載體，也有使用HashMap的，可以根據題目來決定要使用哪種．

我們將昨天的程式碼稍微修改一下，讓在計算的時候帶著Memo．

fun fibonacciWithMemoVersion(n: Int): Int {
    return when (n) {
        0 -> {0}
        1 -> {1}
        else -> {
            val memoArray = IntArray(n+1)//建立Memo Array
            memoArray[0] = 0
            memoArray[1] = 1
            fibonacciWithMemoHelper(memoArray, n)
        }
    }
}

fun fibonacciWithMemoHelper(memoArray: IntArray, n: Int): Int {
    return when {
        n == 0 -> {
            0
        }
        memoArray[n] != 0 -> {//已經在Memo裡面有計算過了
            memoArray[n]
        }
        else -> {
            memoArray[n] =
                fibonacciWithMemoHelper(memoArray,n-1)+ fibonacciWithMemoHelper(memoArray,n-2)
            //計算新的數據
            memoArray[n]
        }
    }
}

讓我們來比較一下，利用measureTimeMillis來計算時間

fun main() {
    val n = 30
    println("N = $n")

    val timeCostNormal = measureTimeMillis {
        val ans = fibonacci(n)
        println("Normal version $ans")
    }

    val timeCostMomo = measureTimeMillis {
        val ans = fibonacciWithMemoVersion(n)
        println("Memo version $ans")
    }

    println("TimeCostNormal:$timeCostNormal")
    println("TimeCostMomo:$timeCostMomo")
}

先跑跑看n = 30

普通版本花費時間是7秒，而Memo版本不到1秒

但在n = 40 的版本，差距就越發的明顯

普通版本花費時間大幅上升，而Memo版本時間沒有增加．

為什麼有如此大的差距，因為Memo版本所有的子問題都只要計算一次．當計算後再次遇到同樣的子問題，就能省略．

也就因此，不再需要進行迴圈計算．

我們來計算時間複雜度，子問題的個數是f(0),f(1)．．．．f(n) ，所以是O(N)

而解決一個子問題，只需要去Memo內拿取已經計算好的子問題答案，而若未計算的子問題，同樣也只需要計算一次，沒有迴圈計算，所以子問題的時間複雜度為O(1)

兩者相乘，使用Memo版本的複雜度降為了O(N)，也難怪在N變大時，所花費的時間沒有什麼變化．比起暴力計算，花費低上許多．

今天我們使用了Memo來作為輔助．明天我們會來使用DP Table．