Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Example:

Input:  n = 5
Output: 5

Approach

Java

public class FibonacciNumber {
    public static void main(String[] args) {
        int n = 5;
        System.out.println(fib(n));
    }

    // method to find the fibonacci

    static int fib(int n)
    {
        if (n <= 1)
            return n;
        int dp[]=new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

//function to find the fibonacci

int fib(int n)
{
    if (n <= 1)
        return n;
    int dp[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

int main()
{
    int n = 5;
    cout << fib(n);
    return 0;
}