Dynamic Programming(Introduction)

When I started studying DP, I found it extremely frustrating as I wasn’t able to approach the problem myself. Later on, After a lot of practice and forcing myself not to give up, I was able to understand how to approach a DP problem. So, endure this initial phase of understanding DP!

Before you move on to DP, it is very important to understand the concept of recursion

DSA Day-13

What is Dynamic Programming?

Dynamic Programming is an algorithmic technique based on storing results of previous computations and using it to reach the required solution. It divides a particular problem into subproblems and stores result of each subproblem to find the solution of the actual problem.

Example:

Fibonacci (n) = 1; if n = 0
Fibonacci (n) = 1; if n = 1
Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2)

If one needs to find fib(5), what will they do? Try thinking yourself!!!

In dynamic programming, we trade space for time, i.e., instead of calculating all the states taking a lot of time but no space, we take up space to store the results of all the sub-problems to save time later.

How to identify DP?

1. Most DP problem asks to maximise or minimise certain quantities or counting arrangements under given conditions.
2. OverLapping Sub-problems: Many subproblems overlap to form the actual problem and hence by finding solution of each subproblem, we can find the actual result.

Memoization

Memoization is an optimization technique used to improve time complexity by storing the results of expensive function calls and returning the cached result when the same inputs occur again. It is similar to what we did in Fibonacci series.

Refer to the following code for fibonacci:

void fib () {
        fibresult[0] = 1;
        fibresult[1] = 1;
        for (int i = 2; i<n; i++)
           fibresult[i] = fibresult[i-1] + fibresult[i-2];
    }

Do you realise what we did in the above code?

We created an array fibresult[] where:

fibresult[] = [1,1, ……. ]

In the above array, we store the result of each computation from 2 till the required integer and use it to compute the final result.

for example, to compute fibresult[2] = fibresult[2–1] + fibresult[2–2]

= fibresult[1] + fibresult[0] = 1+1 = 2

Now the array becomes: fibresult[] = [1,1,2,….]

fibresult[3] = fibresult[3–1] + fibresult[3–2]

= fibresult[2] + fibresult[1] = 2+1 = 3

fibresult[] =[1,1,2,3…..]

and so on…

Hope you find it useful!!! Follow @placement_preparation and stay updated with all the latest stories.