# Fibonacci Numbers Problem – Dynamic Programming

Find nth fibonacci number.

The Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

The next number is found by adding up the two numbers before it.

Let F[i] be the ith fibonacci number

``````F[0]=0
F[1]=1
F[i]=F[i-1]+F[i-2]``````

Solution using Recursion

``````using System;
namespace Fibonaccinumber{
class Program
{
static void Main()
{
Console.WriteLine("Enter the Number");
var result = Fibonacci(n);
Console.WriteLine(\$"Fibonacci number is: {result}");
}

static int Fibonacci(int n)
{
if (n <= 1)
return n;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}

}``````

#### Solution Dynamic Dynamic Programming

``````using System; namespace Fibonaccinumber{
class Program
{
static void Main()
{
Console.WriteLine("Enter the Number");
var result = Fibonacci(n);
Console.WriteLine(\$"Fibonacci number is: {result}");
}

static int Fibonacci(int n)
{
var arr = new int[n + 1];
arr[0] = 0;
arr[1] = 1;
for (var i = 2; i <= n; i++)
arr[i] = arr[i - 1] + arr[i - 2];
return arr[n];
}
}

}``````