# Fibonacci series

The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones. This sequence is not just a mathematical curiosity; it has found applications in various fields like computer science, finance, and nature itself. In this context, we'll explore how to generate the Fibonacci series efficiently using dynamic programming.

## Problem Statement

Given a size `n`, the Fibonacci series involves generating the first `n` numbers of the sequence. For instance, if `n` is 5, the series would be 0, 1, 1, 2, 3.

## Example

For `n = 12`, the Fibonacci series would be 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.

## Idea to Solve

The Fibonacci series can be generated using an iterative approach, commonly known as dynamic programming. Instead of recursively recalculating values, we store previously computed values to avoid redundant calculations.

## Pseudocode

``````function generateFibonacci(size):
if size <= 1:
print 0
else:
result = new array of size
result[0] = 0
result[1] = 1
for i from 2 to size:
result[i] = result[i-1] + result[i-2]
print result``````

## Algorithm Explanation

1. The function `generateFibonacci` takes the size `n` as input.
2. If `n` is less than or equal to 1, we directly print 0 and return.
3. Otherwise, we create an array `result` to store the Fibonacci series.
4. We initialize the first two values of `result` as 0 and 1, respectively.
5. Using a loop, we start from index 2 and iteratively compute the Fibonacci numbers based on the previous two values.
6. The calculated series is printed as the final output.

## Code Solution

``````//C Program
//Fibonacci series
//By dynamic programming
#include<stdio.h>

//Display Fibonacci series of given size
void fib(int size)
{
if(size<=1)
{
printf("%d\n",0 );
}
else
{
//Store fibonacci series
int result[size];

//Set initial values
result[0] = 0 ;
result[1] = 1 ;

for (int i = 2; i < size; ++i)
{
//Use old transaction value
result[i] = result[i-1] + result[i-2];
}
//Show fibonacci series
for (int i = 0; i < size; ++i)
{
printf("%3d",result[i]);
}
printf("\n");
}

}

int main()
{
//Test Case
fib(5);
fib(12);
return 0;
}```
```

#### Output

``````  0  1  1  2  3
0  1  1  2  3  5  8 13 21 34 55 89``````
``````// C++ Program
//Fibonacci series
//By dynamic programming
#include<iostream>

using namespace std;
class DynamicExample {
public:

//Display Fibonacci series of given size
void fibonacci(int size) {
if (size <= 1) {
cout << "0\n";
} else {
int *result = new int[size];
//Set initial values
result[0] = 0;
result[1] = 1;
for (int i = 2; i < size; ++i) {
//Use old transaction value
result[i] = result[i - 1] + result[i - 2];
}
//Show fibonacci series

for (int i = 0; i < size; ++i) {
cout << " " << result[i];
}
cout << "\n";
}
}
};
int main() {
DynamicExample obj =  DynamicExample();
//Test Case
obj.fibonacci(5);
obj.fibonacci(12);
return 0;
}```
```

#### Output

`````` 0 1 1 2 3
0 1 1 2 3 5 8 13 21 34 55 89``````
``````// Java Program
//Fibonacci series
//By dynamic programming

public class DynamicExample
{
//Display Fibonacci series of given size
public void fibonacci(int size)
{
if (size <= 1)
{
System.out.print("0\n");
}
else
{
//Store fibonacci series
int[] result = new int[size];

//Set initial values
result[0] = 0;
result[1] = 1;

for (int i = 2; i < size; ++i)
{
//Use old transaction value
result[i] = result[i - 1] + result[i - 2];
}
//Show fibonacci series

for (int i = 0; i < size; ++i)
{
System.out.print("  "+ result[i]);
}
System.out.print("\n");
}
}

public static void main(String[] args)
{
DynamicExample obj = new DynamicExample();
//Test Case
obj.fibonacci(5);
obj.fibonacci(12);

}
}```
```

#### Output

`````` 0 1 1 2 3
0 1 1 2 3 5 8 13 21 34 55 89``````
``````// C# Program
// Fibonacci series
// By dynamic programming
using System;
public class DynamicExample {
//Display Fibonacci series of given size
public void fibonacci(int size) {
if (size <= 1) {
Console.Write("0\n");
} else {
int[]
//Store fibonacci series
result = new int[size];
//Set initial values
result[0] = 0;
result[1] = 1;
for (int i = 2; i < size; ++i) {
//Use old transaction value
result[i] = result[i - 1] + result[i - 2];
}
//Show fibonacci series

for (int i = 0; i < size; ++i) {
Console.Write(" " + result[i]);
}
Console.Write("\n");
}
}
public static void Main(String[] args) {
DynamicExample obj = new DynamicExample();
obj.fibonacci(5);
obj.fibonacci(12);
}
}```
```

#### Output

`````` 0 1 1 2 3
0 1 1 2 3 5 8 13 21 34 55 89``````
``````<?php
// Php Program
//Fibonacci series
//By dynamic programming
class DynamicExample {
//Display Fibonacci series of given size

public 	function fibonacci(\$size) {
if (\$size <= 1) {
echo("0\n");
} else {
//Store fibonacci series
\$result = array_fill(0, \$size, 0);
//Set initial values
\$result[0] = 0;
\$result[1] = 1;
for (\$i = 2; \$i < \$size; ++\$i) {
//Use old transaction value
\$result[\$i] = \$result[\$i - 1] + \$result[\$i - 2];
}
//Show fibonacci series

for (\$i = 0; \$i < \$size; ++\$i) {
echo(" ". \$result[\$i]);
}
echo("\n");
}
}
}

function main() {
\$obj = new DynamicExample();
//Test Case
\$obj->fibonacci(5);
\$obj->fibonacci(12);

}
main();```
```

#### Output

`````` 0 1 1 2 3
0 1 1 2 3 5 8 13 21 34 55 89``````
``````// Node Js Program
//Fibonacci series
//By dynamic programming
class DynamicExample {
//Display Fibonacci series of given size
fibonacci(size) {
if (size <= 1) {
process.stdout.write("0\n");
} else {
//Store fibonacci series
var result = Array(size).fill(0);
//Set initial values
result[0] = 0;
result[1] = 1;
for (var i = 2; i < size; ++i) {
//Use old transaction value
result[i] = result[i - 1] + result[i - 2];
}

//Show fibonacci series

for (var i = 0; i < size; ++i) {
process.stdout.write(" " + result[i]);
}

process.stdout.write("\n");
}
}
}

function main(args) {
var obj = new DynamicExample();
//Test Case
obj.fibonacci(5);
obj.fibonacci(12);
}

main();```
```

#### Output

`````` 0 1 1 2 3
0 1 1 2 3 5 8 13 21 34 55 89``````
``````#  Python 3 Program
# Fibonacci series
# By dynamic programming

class DynamicExample :
# Display Fibonacci series of given size
def fibonacci(self, size) :
if (size <= 1) :
print("0\n", end = "")
else :
result = [0] * size
# Set initial values
result[0] = 0
result[1] = 1
i = 2
while (i < size) :
# Use old transaction value
result[i] = result[i - 1] + result[i - 2]
i += 1

# Show fibonacci series
i = 0
while (i < size) :
print(" ", result[i], end = "")
i += 1

print("\n", end = "")

def main() :
obj = DynamicExample()
obj.fibonacci(5)
obj.fibonacci(12)

if __name__ == "__main__":
main()```
```

#### Output

``````  0  1  1  2  3
0  1  1  2  3  5  8  13  21  34  55  89``````
``````# Ruby Program
# Fibonacci series
# By dynamic programming
class DynamicExample
# Display Fibonacci series of given size
def fibonacci(size)
if (size <= 1)
print("0\n")
else
result = Array.new(size) {0}
# Set initial values
result[0] = 0
result[1] = 1
i = 2
while (i < size)
# Use old transaction value
result[i] = result[i - 1] + result[i - 2]
i += 1
end
# Show fibonacci series
i = 0
while (i < size)
print(" ", result[i])
i += 1
end
print("\n")
end
end
end
def main()
obj = DynamicExample.new()
obj.fibonacci(5)
obj.fibonacci(12)
end
main()```
```

#### Output

`````` 0 1 1 2 3
0 1 1 2 3 5 8 13 21 34 55 89
``````
``````// Scala Program
//Fibonacci series
//By dynamic programming
class DynamicExample {
//Display Fibonacci series of given size
def fibonacci(size: Int): Unit = {
if (size <= 1) {
print("0\n");
} else {
var result: Array[Int] = Array.fill[Int](size)(0);

//Set initial values
result(0) = 0;
result(1) = 1;
var i: Int = 2;
while (i < size) {
//Use old transaction value
result(i) = result(i - 1) + result(i - 2);
i += 1;
}
//Show fibonacci series
i = 0;
while (i < size) {
print(" " + result(i));
i += 1;
}
print("\n");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: DynamicExample = new DynamicExample();
obj.fibonacci(5);
obj.fibonacci(12);
}
}```
```

#### Output

`````` 0 1 1 2 3
0 1 1 2 3 5 8 13 21 34 55 89``````
``````// Swift Program
//Fibonacci series
//By dynamic programming
class DynamicExample {
//Display Fibonacci series of given size
func fibonacci(_ size: Int) {
if (size <= 1) {
print("0\n", terminator: "");
} else {
var result: [Int] = Array(repeating: 0, count: size);
//Set initial values
result[0] = 0;
result[1] = 1;
var i: Int = 2;
while (i < size) {
//Use old transaction value
result[i] = result[i - 1] + result[i - 2];
i += 1;
}
//Show fibonacci series
i = 0;
while (i < size) {
print(" ", result[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
}
}
func main() {
let obj: DynamicExample = DynamicExample();
obj.fibonacci(5);
obj.fibonacci(12);
}
main();```
```

#### Output

``````  0  1  1  2  3
0  1  1  2  3  5  8  13  21  34  55  89``````

## Time Complexity

The time complexity of this algorithm is O(n) because we iteratively calculate each Fibonacci number once using the dynamic programming approach.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.