Dynamic programming is a programming technique that is used to solve a certain set of problems. It has many real-world applications in many areas like biology, finance, number theory, gaming, etc.

What is Dynamic programming?

Dynamic programming is basically an optimization technique, which means that we can get solutions to the same problem using other programming techniques like recursion or divide and conquer but dynamic programming can be used to solve the problem optimally.

A problem needs to have two properties, for it to be solved using dynamic programming.

1. Optimal substructure

"A problem exhibits optimal substructure if an optimal solution to the problem contains within it the optimal solution to subproblems." What it means is that if we can reach the optimal solution to the problem by getting the optimal solution for the subproblems, then the problem has the property of optimal substructure.

Example

Take the classic dynamic programming problem...

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Let us say, we are taking n = 4

To solve a dynamic programming problem, you need the following steps...

Step 1: Write the objective function(f(i), let's say, f(i) stands for the total number of distinct ways to reach the top)

Step2: Writing the base cases (Those cases for which we do not need a computer to compute)

f(0) = 1 (for ground, as there is only one way you can be on the ground)

f(1) = 1(there is only one way to reach the first step)

f(2) = 2 (there are exactly two ways, either you can take 1 step two times, or you can take 2 steps at a time). So these are the base cases for this problem, for which we do not need even a computer to calculate...

Now, as you see a pattern, if we can get the number of ways to reach 1, and 2nd steps, we can get the number of ways to reach the third step also...

f(3) = f(2) + f(1), as we can reach from the 2nd step or from the 1st step (a maximum of two steps at a time is allowed), in this way we can get the number of required to reach for the top also.

Now focus on one thing, by knowing the optimal solutions to subproblems we are getting the optimal solution to the whole problem, this is the property of optimal substructure shown to you here.

Step 3: Writing the recurrence relation(In mathmatics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of previous terms)

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

2. Overlapping subproblems

When a recursive algorithm revisits the same problem repeatedly, we say that the optimization problem has overlapping subproblems. Dynamic programming algorithms typically take advantage of overlapping subproblems by solving each subproblem once and then storing the solution in a table where it can be looked at when needed, using constant time lookup, in python for example by using a dictionary.

If a problem is having similar subproblems, then it comes in the category of overlapping subproblems.

Example

In the above problem of climbing the nth stair, let us find out overlapping subproblems

As you can see, say for n = 4, from the above recurrence relation

f(4) = f(3) + f(2)

f(3) = f(2) + f(1)

f(2) = f(1) + f(0), as you can see there are problems which are needed to be calculated again and again, so these are basically overlapping subproblems, so instead of calculating the problems, again and again, we will solve them effectively at a place, preferably in a dictionary, which is known as memoization.

Good resources for learning Dynamic programming

Check the below playlist