LeetCode 筆記 - 509. Fibonacci Number

Posted on 標籤
LeetCode 費氏數列計算解析。本文展示如何利用動態規劃（DP）與查表法（Memoization）來儲存中間計算結果，避免傳統遞迴導致的重複運算與效能浪費。這是一篇理解遞迴優化與動態規劃入門的最佳實踐筆記。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 509. Fibonacci Number

請計算費氏數列的結果

解題思維

就簡單 Dynamic programming 避免重複的計算即可

剩下就跟著定義實作即可

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    count = [inf] * 31
    count[0] = 0
    count[1] = 1
    def fib(self, n: int) -> int:
        if self.count[n] != inf:
            return self.count[n]

        result = self.fib(n - 1) + self.fib(n - 2)
        self.count[n] = result
        
        return result

也許你也會想看看