Dynamic Programming

Dynamic programming is mainly used to provide optimization for recursion. In the recursive solution, if we are using the function with the same parameters, we can avoid re-computation with dynamic programming. The concept in dynamic programming is to store the subproblem solution and use it in a later part of processing.

We can understand dynamic programming by getting the i^th Fibonacci number.

The Fibonacci series contains numbers that have the following relation:

$$F(n) = F(n-1) + F(n-2)$$

$$F(0) = F(1) = 1$$

This means that every number in the series will be the sum of the previous two numbers.

The series will look like this:

$$1,1,2,3,5,8,13,21...$$

The problem in generating the nth Fibonacci number. We can solve this problem by using recursion.

Here is the recursive version of the solution. The base case is when the index is 1 or 2 (assuming indexing starts from 1). The answer is 1. Otherwise, we calculate the top with the sum of the last two numbers. For example, at the fifth index, we call the function for the forth index,third index, and sum the value.