Hello, In this article I will discuss about the dynamic programming. How we can use the concept of dynamic programming to solve the time consuming problem. I will use the example of the calculating the Fibonacci series. This is only an example of how we can solve the highly time consuming code and convert it into a better code with the help of the in memory cache.
Dynamic Programming
Whenever we are about to solve a problem which deals with the repeated occurrence of the same problem, we can say that we solving the same problem again and again. This multiple solving of the same problem can lead to explosion of the same problem which can be time consuming.
Instead of finding the solution of the same problem again and again we can just solve the problem once and keep the solution in cache to be used for future calculations.
Fibonacci Series
Fibonacci series is the number list in which the number(N) is the sum of previous two numbers.
1 1 2 3 5 8 13 21 34…
Now to calculate it using C# program we have to have a recursive set of instructions written where the input will be the number of element for which we have to find a Fibonacci number.
Lets see the code below.
public static long Fibonacci(long n)
{
if (n <= 1)
return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Now if you calculate the Fibonacci for a number using the above program for smaller number up to may be 40. You will get the result immediately. But suppose if you want to calculate the Fibonacci for a bigger number e.g. 60 you may have to keep waiting and the there would not be any result.
Why is it so?
The reason for the same is explosion of the same logic to be calculated again and again.
E.g To calculate the Fibonacci of 5, Fibonacci of 1 is getting called 6 times as shown in the below code.
As we have seen there is explosion of identical sub problems.
Just for a better understanding of the problem have a look at the below figure. To calculate the Fibonacci of 30, the number of times Fibonacci of 1, 2 and 3 is called for tremendous number of times.
What can we do solve the same sub problem again and again?
A very easy solution to solve the problem of calculating the same sub problem again and again is to have a cache of the solutions for the future use.
With the help of cache we can easily get the result of any number for the Fibonacci.
Have a look at the below code to find the Fibonacci using cache.
static long[] cache = new long[200];
public static long FibonacciUsingCache(long n)
{
if (n <= 1)
cache[n] = 1;
if (cache[n] == 0)
cache[n] = FibonacciUsingCache(n - 1) + FibonacciUsingCache(n - 2);
return cache[n];
}Hence we have been able to optimize the solution of finding the Fibonacci using cache in C#.
This is one of the example of dynamic programming.
In our day to day programming if we are finding the solution to same problem again and again to come final solution, in that case we can always use cache to keep the solutions for future use.