How to get nth Fibonacci number in swift using dynamic programming ?

Fibonacci is series of numbers like 0 1 1 2 3 5… Actually its sum of previous two elements. In this article we discuss 3 method to get nth fibonacci number

#1 Using Dynamic programming

Store computed result into array so whenever next fib(.. called we are using that value. In short we can say that we are overlapping subproblems. In the below code `dp` act as memoization element, initially we have assigned dp element as -1 till n+1 time, where n denotes the desired nth fib number

// Time Complexity: O(n)+O(1)
// Space Complexity: O(n)+ O(n)
func fib(_ n: Int, _ dp: inout [Int]) ->Int {
    if n <= 1 { return n }
    if dp[n] != -1 {return dp[n]}
    dp[n] = fib(n-1, &dp) + fib(n-2, &dp)
    return dp[n]
}
var n = 5
var dp: [Int] = Array.init(repeating: -1, count: n+1)
print(fib(n, &dp))

#2 Using Recursion.

// TC: 2^n
// SC: 2^n
func fib(_ n: Int) ->Int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

#3 Using single loop(Best Approach).

// TC: O(n)+O(1)
// SC: O(1)
func fib(_ n: Int) ->Int {
    if n <= 1 {return n}
    var prev2 = 0
    var prev1 = 1
    for _ in 2...n {
        let curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    }
    return prev1
}
var n = 5
print(fib(n))// print 5