Technical DP

DYNAMIC PROGRAMMING

O verview

Dynamic programming(DP) is a general, powerful algorithm design technique coined by American mathematician Richard Belman. Its heavily used in graphs, AI, ML, and many more difficult sounding fields and areas.Used to cut down the time-consuming techniques for solving a program. Basically,

 ●                 Dynamic = time varying aspect of the problem

●                 Programming(British English) = optimization(American English)

So we can say dynamic problem = careful brute force method

DP  = Subproblems + "Reuse"

That is to say, dividing the problems into subproblems and reusing the method used once to solve the subproblems again and again thus maintaining efficiency and accuracy.

U nderstanding with an example

Let's take the example of Fibonacci Numbers.Before reading forward try to write an algorithm to generate the sum of the ‘n’ Fibonacci numbers in a recursive manner,, n being inclusive.

We all already know F1 = F2 =1 and Fn=Fn-1 + Fn-2

Now there can be 2 methods of solving the problem,

NAIVE RECURSIVE ALGORITHM	MEMOIZED DP ALGORITHM
fib(n):	memo={}
if(n<=2): f=1	fib(n):
else f= fib(n-1)+fib(n-2)	If n is in memo : return memo[n]
return f;	if(n<=2) : f=1
	else f= fib(n-1)+fib(n-2)
	memo[n]=f
	return f

The first naive method is very obvious and time consuming while the other makes use of memoization. Its nothing but remembering all that has been done before or simply memorizing.

C onclusion

Thus, our previous formula can be further refined to,

DP =Recursion+ Memoization +

Guessing

●                 Recursion as is exponential by own and is used again again

●                 Memoization is to remember and reuse the solution to subproblemsGuessing as to figure out what should be used, try all guesses and take the best one.

That provide us with the basic idea of DP and we are now a little familiar with this amazing and efficient problem solving approach.

By Shivangi Tiwari