Mastering DP #2: Climbing Stairs problem and Greedy vs DP intuition building
We've understood the basic concept of dynamic programming in the last article. Let's understand more with another simple example
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's observe few things first
What if we only have one stair?
The number of ways to climb that stair will always be 1.
What if we only have to climb two stairs?
Either one step at a time or 2 steps at once. The number of ways to climb 2 stairs will be 2.
What if we only have to climb 3 stairs?
We've already found out the number of ways to climb 2 stairs.
If we want to go to the 3rd stair from 2nd. We only have one way. Take one step up from 2nd stair.
So The number of ways to climb 3 stairs will be 2+1 = 3
In every DP Problem, we need to check 2 things
Optimal substructure: This means we can use the solution of 1 and 2 stairs to find the solution of the 3rd stair.
Overlapping subproblem: Is the same problem repeating again and again?
if we see these two properties in any problem that means we can consider solving that problem with the help of dynamic programming.
Let's define a skeleton to solve any DP problem. It's a 4-step process
The element of Choice: In every problem, we have to find what are the choices we have.
Define state: Represent the state of your problem with a data structure. We'll figure out, how to do that in 2 mins.
Find recurrence relation: Find the repeating subproblem
Final stage: Find out what state will give me my final answer?
Let's replicate the skeleton in our current problem
The element of choice:
We only have two choices here. We can take either 1 step or 2 steps at a time. That means we can be coming from the i-1 stair or i-2 stair.
Define state: We have to store the number of ways to reach ith stair from 0th stair. We can represent this simply by using an array
Ways[i] can represent the number of ways to reach ith stair from 0.
Recurrence relation: Utilise the above two pieces of information to create a recurrence relation
- Come from (i-1) step
- Come from (i-2) step
In case 1:
We have only one way to move from i-1 to i. There's only one way. So total ways, in this case, would be ways[i] = ways[i-1]*1;
In case 2:
Now understand this calmly, how many ways we have to go from i-2 to i. We can take 2 steps at a time. So we only have 1 way to go from i-2 to I by taking 2 steps at a time.
Now some will think that we can also take 1 step, 2 times. To go from i-2 to i. But that case is already handled in case 1, From i-1 to i. Here we are only considering i-2 to i directly.
Ways[i] = ways[i-2]*1;
Final State: As we have to climb n stairs. ways[i] stores the possible distinct ways to climb i stairs. So ways[n] will give us our final solution.
If we add the result of case 1 and case 2. We'll get all the distinct ways to climb to the top. Now Let's see the actual code
Greedy vs DP:
While considering elements of choice, if we know the best choice amongst all, then we can apply a greedy approach but when we need to explore all the elements of choices then we need dynamic programming.
Two terms are very famous while encountering dynamic programming problems. Let's see what's mutually exclusive and mutually exhaustive means
Mutually exclusive: In the last problem, we can either take 1 step or 2. So there is no overlapping in the element of choices. Then these are mutually exclusive
Mutually exhaustive: No case should be left out. In the last problem either you can come from i-1 or i-2 states. So these are mutually exhaustive.
In the next article, we'll try to understand the intuition and implementation of a very famous DP problem Longest Increasing subsequence
I faced this problem in a lot of company interviews. See you in the next article.