สร้างลำดับฟีโบนัชชี (Fibonacci Series) ด้วย Dynamic Programming

ลำดับฟีโบนัชชี: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

สูตร: F(n) = F(n-1) + F(n-2) โดย F(0)=0, F(1)=1

วิธี Reursive แบบธรรมดาจะมีการคำนวณซ้ำมาก (Exponential Time) ใช้ Dynamic Programming (Bottom-up) เก็บค่าในตาราง → O(n)

ตัวอย่าง Input และ Output

Input: n = 10
Output: 10th Fibonacci Terms: 55

อัลกอริทึม Bottom-up DP

ฟังก์ชัน genFiboSeries(n)

ขั้นตอน:

1. สร้างอาร์เรย์ fibo[n+2]
2. fibo[0] = 0, fibo[1] = 1
3. for i = 2 ถึง n:
   • fibo[i] = fibo[i-1] + fibo[i-2]
4. คืน fibo[n]

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

int genFibonacci(int n) {
    int fibo[n+2];
    fibo[0] = 0;
    fibo[1] = 1;
    for (int i = 2; i <= n; i++) {
        fibo[i] = fibo[i-1] + fibo[i-2];
    }
    return fibo[n];
}

int main() {
    int n;
    cout << "Enter number of terms: "; cin >> n;
    cout << n << "th Fibonacci Terms: " << genFibonacci(n) << endl;
    return 0;
}

Output

Enter number of terms: 10
10th Fibonacci Terms: 55

ความซับซ้อน

• Time: O(n)
• Space: O(n) (สามารถลดเป็น O(1) ได้โดยเก็บแค่ 2 ตัวล่าสุด)

การเพิ่มประสิทธิภาพ Space O(1)

int genFibonacciOptimized(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

ขยาย: Matrix Exponentiation O(log n)

ใช้การยกกำลังเมทริกซ์: [[1,1],[1,0]]^n = [[F(n+1), F(n)], [F(n), F(n-1)]]