動態規劃 (DP)

解題思路

費波那契數列的定義是 ，，並且 對於任意 成立。

這個遞迴關係可以用動態規劃來實現，只需要記錄 和 作為初始值，然後不斷更新 的值一直到 為止。

這樣的實作時間複雜度和空間複雜度都是 。但是，由於 只和前兩項有關，我們可以用「滾動陣列」的方法將空間複雜度降低到 ，只需要用兩個變數來存儲 和 即可。以下的程式碼將示範這種優化方法。

別閉門造車，一起準備面試吧！
在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷諮詢！
我們將幫助你撰寫一份出色的履歷表，讓你在眾多求職者中脫穎而出。從技術主管的視角切入，幫助你在履歷上呈現最完美的自己。如果心動的話，就別猶豫啦！趕快把握機會，動動手指投遞履歷吧！立即加入「面試讀書會」，和大家一起準備面試！

職涯諮詢	加入讀書會 (邀請碼：1288)

程式

class Solution {
    fun fib(n: Int): Int {
        var a = 0
        var b = 1
        if (n == 0) return a
        else if (n == 1) return b
        var c = a + b
        for (i in 2..n) {
            c = a + b
            a = b
            b = c
        }
        return c
    }
}

複雜度分析

• 時間複雜度:
  。

• 空間複雜度:
  。

　DP 還可以用 top-down 搭配 memoization 的方式求解哦，一起來學習！

別閉門造車，一起準備面試吧！

在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷諮詢！

履歷諮詢	加入讀書會 (邀請碼：1288)