用動態規劃算費氏數（Fibonacci）
/ Fibonacci = fib-oh-NAH-chee /
費氏數從 0, 1, 1, 2, 3, 5, 8, 13, ... 開始，每個數都是前兩個之和。它們是動態規劃課本上的第一個例子，不是因為它們本身有多重要，而是因為它們以縮影展現了整個概念：一個慢得災難的天真遞迴、一個解釋這份慢的重疊、以及一行修好它的快取。如果你懂得為何慢的版本慢、快的版本快，你就懂了動態規劃的核心。
定義它的遞迴是 fib(n) = fib(n-1) + fib(n-2)，基底情況為 fib(0) = 0 與 fib(1) = 1。直接寫成遞迴雖正確，卻要約 2^n 次呼叫，因為 fib(n-2) 被 fib(n-1) 和 fib(n) 各算一遍，重複往樹下爆炸（這是最純粹形式的重疊子問題）。動態規劃注意到要算的相異值總共只有 n+1 個。由上而下，你加一個記憶表使每個 fib(k) 只跑一次：O(n) 時間。由下而上，你以 i 遞增填一個陣列 f[0..n]，f[i] = f[i-1] + f[i-2]：同樣 O(n) 時間。又因為每個 f[i] 只需前兩格，你可以把陣列丟掉、保留兩個滾動變數，得到 O(n) 時間與 O(1) 額外空間。
費氏數值得細想，因為每個能放大到困難動態規劃的概念，都在這裡乾淨地現身：狀態就是索引 n；轉移是兩個前驅相加；基底情況是兩個種子；計算順序是 i 遞增；而那個空間最佳化（兩個變數）正是滾動陣列概念最樸素的裝扮。它也帶來關於漸進的誠實一課：天真的 O(2^n) 與動態規劃的 O(n) 給出一模一樣的答案，但對 n = 50，一個瞬間完成，另一個卻做超過十億次呼叫——輸出相同，成本天差地別。（順帶一提，還有更快的方法——矩陣冪公式以 O(log n) 執行——但那超出了基本動態規劃的範圍。）
fib(6) 用慢方法要做 25 次呼叫；用動態規劃則以五次加法算出 f[2]=1, f[3]=2, f[4]=3, f[5]=5, f[6]=8。滾動變數形式：a,b = 0,1；做六次更新 (a,b)=(b,a+b) 即得 a = 8，完全不用陣列。
同樣的答案，但動態規劃做 n 次加法，天真遞迴卻做約 2^n 次呼叫。
費氏數顯示動態規劃與天真遞迴給出相同答案卻成本天差地別——漸進談的是規模成長，而非正確性。也要注意這裡動態規劃的 O(n) 並非最快；矩陣冪法可達 O(log n)，但那超出了動態規劃基礎的範圍。