Dynamic Programming

                Suppose, There are 5 Apples in the basket. And If I put 2 apples into the basket, Now How many apples in the basket? you must be wondering what kind of stupid question is this? Obviously, there are 7 apples. If I ask how can you be sure about apples without counting it? again such a stupid question, I already told you there are 5 apples and I put 2 apples in it, So 5 + 2 apples are 7 apples. But In this case also, you don’t count apples, you just add them and tell the answer, right? I am right now focusing on counting procedure itself, BUT counting from zero is not necessary when one already know the previous number of apples, If one does it, It is just waste of time. Here we save time by applying the previous value.

                Let`s ask another similar kind of question. Which year is going on? 2016.. oops 2017(it happens, its 1^st January ). Ok if I ask you after five years which year will be going on? 2022 right. Now another five years from it? 2027. To calculate 2027 we don’t start from 2017 we just add 5 to 2022. Because it is again time wasting procedure to start calculating from beginning when we have some intermediate result.

                Suppose one want to find out student with highest it in class. And the school has 20 different classes. So the result of highest IQ students is 20 student with highest IQ in particular class. NOW if one want to find out Highest IQ student in the school. So there are two ways to find out we can consider all students in school OR we can use the result of highest IQ student in particular class which is already obtained. The second method is more efficient than the previous one.

  

Find Patterns AND eliminate repetitive tasks.

              Find out a solution more efficiently using previously obtained results is called Dynamic programming in computer science. First, we divide problems into smaller one like divide-and-conquer, then find out patterns/similarities into them and solve one unique problem only once and use it to obtained Big problem solution. Dynamic programming eliminates repetitive task in order to get the better solution. If we find patterns into sub-problems of given problem we can apply dynamic programming.

                Finding factorials up to given number can be solve using dynamic programming. Factorial of any number is the multiplication of all the numbers from 1 to that particular number. Brute-Force approach (Simple – Straight Forward) method is to calculate every number factorial and add to array.

                Like,

                                Factorial (5) = 5 x 4 x 3 x 2 x 1

                                                     = 120

	/*
	Brute-Force Approach
	Funtion to calculate up to N Factorials
	*/
	int[] factorialBF(int n)
	{
	int a[n+1],i,j; // factorials array
	a[0]=1;
	// loop for array
	for(i=1;i<=n;i++)
	{
	a[i]=1;
	//loop for calculate i th Factorial
	for(j=1;j<=i;j++)
	{
	a[i]=a[i]*j;
	}
	}
	return a;
	}

view raw FactBF.cpp hosted with ❤ by GitHub

If we want to apply dynamic programming, we have to find pattern/relation between sub-problems. To find series of factorials up to N, sub-problem is to find out factorial of given number. Let's find out pattern/relation between different factorial.

                Factorial (6) = 6 x 5 x 4 x 3 x 2 x 1

                                       = 6 x Factorial(5)  (Because 5x4x3x2x1 = Factorial(5))

We can use this relation to implementing

Dynamic Programming. Now when we find out factorial(N) we add to array and Then for finding Factorial(N+1) we can use the previously obtained result to eliminate repetitive calculations. Demonstrated in C/C++.

	/*
	Dynamic Programming Approach
	Funtion to calculate up to N Factorials
	*/
	int[] factorialDP(int n)
	{
	int a[n+1],i,j; // factorials array
	a[0]=1;
	for(i=1;i<=n;i++)
	{
	a[i] = i * a[i-1];
	}
	return a;
	}

view raw FactorialDP.cpp hosted with ❤ by GitHub

Do Dynamic Programming in your life, Don’t repeat 2016 mistakes in 2017.