509 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,
::: tip 💡 Use fibCache = new Dictionary<int, int>()
to improve performance :::
Given n, calculate F(n).
Example 1:
Example 2:
Example 3:
C# Solution¶
using System;
using System.Collections.Generic;
namespace Algorithms.Simple
{
public class FibonacciNumber
{
public static int Recursive(int v)
{
if (v <= 1) return v;
return Recursive(v - 1) + Recursive(v - 2);
}
public static int Dynamic(int v)
{
var fibCache = new Dictionary<int, int>();
if (v <= 1) return v;
if (fibCache.ContainsKey(v))
{
return fibCache[v];
}
else
{
fibCache.Add(v, Dynamic(v - 1) + Dynamic(v - 2));
}
return fibCache[v];
}
public static int Cache01Space(int v)
{
if (v <= 1) return v;
var fb0 = 0;
var fb1 = 1;
for (var i = 2; i <= v; i++)
{
var fb = fb0 + fb1;
fb0 = fb1;
fb1 = fb;
}
return fb1;
}
}
}
C# Tests¶
using System;
using Algorithms.Simple;
using Xunit;
namespace AlgorithmTests.Simple
{
public class FibonacciNumberTests
{
[Fact]
public void RecursiveTest1()
{
Assert.Equal(3, FibonacciNumber.Recursive(4));
}
[Fact]
public void DynamicTest1()
{
Assert.Equal(3, FibonacciNumber.Dynamic(4));
}
[Fact]
public void FibCacheO1Space()
{
Assert.Equal(3, FibonacciNumber.Cache01Space(4));
}
}
}