// 1. Recursive approach
func fib(_ n: Int) -> Int {
    guard n > 1 else { return n }
    return fib(n-1) + fib(n-2)
}
// Time Complexity: O(2^n)
// Space Complexity: O(2^n)

// 2.  Iterative approach
func fib(_ n: Int) -> Int {
    var fibs: [Int] = [1, 1]
    (2...n).forEach { i in
        fibs.append(fibs[i - 1] + fibs[i - 2])
    }
    return fibs.last!
}

// Time Complexity: O(n)
// Space Complexity: O(n)

// 3. Iterative approach — Optimized
func fib(_ n: Int) -> Int {
    var a = 1
    var b = 1
    guard n > 1 else { return a }

    (2...n).forEach { _ in
        (a, b) = (a + b, a)
    }
    return a
}
// Time Complexity: O(n)
// Space Complexity: O(1)