Welcome back.
Let's now get into the approach for solving this question.
Now the jump game question can be solved both using dynamic programming as well as the greedy approach.
And we will soon discuss why this is the case.
But remember, whenever you have a question that can be solved both using dynamic programming as well
as the greedy approach, typically the greedy approach will give you a better time complexity.
Now let's get into the nitty gritties.
Why is it that this question can be solved with dynamic programming?
Now for discussing this, let's take an example.
Let's say the array which is given to us is this array over here, which is 23104.
And let me write the indices which go from zero up to four.
Now we start at index zero.
And because the value over here is two, it means that I can make a jump of up to two indices.
Okay.
So I can go from here to here or from here to here.
So these are the two places that I can reach from this index over here.
So notice choices are involved over here.
I can either choose to come to this place or I can choose to come to this place over here.
And when we discuss dynamic programming, this was one of the hints that indicate that probably we can
use dynamic programming.
Now there is another interesting thing that we can see over here.
We start at index zero.
And if I make a jump of one unit, I reach index one.
And if I take a jump of two units, I reach index two.
Okay.
And notice we are having branches over here.
This is another interesting hint that we discussed in dynamic programming, because whenever you have
branches like this, there is a high chance for overlapping subproblems.
Now again, just to take this a little bit deeper from index one, we can either take a jump of one,
2 or 3.
Okay.
So that means I can reach indices two, 3 or 4.
So these would be the branches.
And notice we have two over here.
And we have two over here which indicates the presence of overlapping subproblems.
And again remember this over here represents whether we can reach the last index starting at index two.
So that's the subproblem over here.
And that's the same thing that we have over here.
Whether we can reach the last index starting at index two.
So we have overlapping subproblems.
We have branches we have choices.
And all of this indicates that probably we can use dynamic programming to solve this question.
Also notice that this question has optimal substructure.
And with that I mean that we can use solutions to subproblems to identify the solution for the original
problem.
Again.
For example, notice a subproblem could be whether you can go to index four from index two okay.
That's what we had over here.
And we can use these to identify the solution to the problem okay.
Another example would be if I know the answer to the subproblem which is that I can go from 1 to 4 okay.
And I can do that because I can just take a jump of three units so I can go from 1 to 4.
So knowing this subproblem okay, which is this over here helps me solve the original problem, which
is whether I can go from 0 to 4, which is what we have over here.
And again, notice I can go from 0 to 4 if I can go from 1 to 4, because I can just go from 0 to 1.
That's also possible, right?
So again, notice knowing the solution to subproblems helps me identify the solution to the original
problem at hand.
And therefore this question has optimal substructure.
And we have already seen that there is a high chance that it has overlapping subproblems.
And in fact, we did validate that there are overlapping subproblems.
And for these reasons, we can use dynamic programming to solve this question.
Now a quick side note.
Okay, we will not be covering the dynamic programming approach in detail in this video, but we'll
just build the approach over here.
And I'll give you a separate article in this section where the dynamic programming solutions will be
mentioned.
All right.
Now let's take the example where the array which is given to us is 23104 okay.
And the indices start from zero and go up to four.
Now if I were to draw the recursive tree over here and again, remember whenever you start with dynamic
programming and when you're dealing with a new type of question, always first come up with the recursive
solution, then memorize it, and then you will be in a position to even write the tabulation approach.
So if we take a look at the recursive tree over here, I'm starting at index zero.
And from zero I can get to index 1 or 2.
And from index one I can get to index two, three and four.
We have already discussed that previously.
Now notice what's actually happening over here is that we are following a backtracking or a recursive
approach over here.
And again, it's not typically backtracking in the technical sense where we are making changes to the
state of the problem in place, but rather technically it's just a recursive approach where we will
be exploring all the different paths possible until we either get true or we have explored all the possible
paths and we see that it's not possible.
Right?
So this would be the recursive way of solving this question.
And then you can memorize this by just having a DP table.
So over here you have five elements.
So in the DP table you will also need five cells.
And you will fill every cell with either true or false.
And again what would each cell represent.
For example this cell over here would represent whether you can get to the last index from this cell.
So if you can do that we will fill true over here.
Otherwise we'll have the value false over here okay.
So this is how you can memorize this.
And if you can write the memoization solution for this problem you can definitely write the tabulation
approach or the bottom up approach as well.
Okay.
Now again as I've mentioned, we are not going to discuss this in detail over here because we are dealing
with the greedy approach.
But I will provide you an article with the dynamic programming solutions as well.
All right.
So let's get back.
We have seen that we can solve the jump game question using dynamic programming.
Now let's discuss why we can solve this question using the greedy algorithm.
First of all notice this is an optimization problem because we have discussed that the greedy approach
is used for solving optimization questions.
Now how is this an optimization question?
We are just trying to see whether you can get to the last index.
When you start at the first index, how come this is an optimization problem, right.
So again you can think of this as maximizing the reach within the constraints provided by the elements
of the array okay.
And again with maximizing the reach we mean whether you can reach this position or not.
And the constraints provided by the elements of the array is the value in the array at each position
okay.
Because that determines the number of positions you can jump.
So that's why this is an optimization problem.
All right.
So this is an optimization question.
Now what else is there that can help us identify that.
This is a question that can be solved using the greedy algorithm.
Let's think about that.
So the next thing that helps us identify this as a question that can be solved using the greedy algorithm,
is the fact that this problem follows the greedy choice property.
And again, why is that the case?
This is the case because making locally optimal solutions will help us arrive at the global optimal
solution, which is to identify true or false.
Okay.
And again we're just trying to understand whether we can reach at the last index starting at the first
index.
Now what is the locally optimal choice or the greedy choice that we will be making at every index?
The thing that we will be doing is to jump to the farthest reachable index from each reachable index.
We will soon discuss this in detail when we discuss the greedy approach for solving this question.
Now, if this is not clear to you, let's just assume that this is true because this will soon become
clear to you in the next video when we discuss this in detail.
But because this is true, and we are just assuming this to be true at this point, the question follows
the greedy choice property.
And this also helps us understand that this is a question that can be solved using the greedy algorithm.
All right.
In the next two videos, let's discuss two greedy approaches that we can use, which are pretty similar,
with the only difference that in one case we will be going from the beginning to the end, and the other
case we will be going from the ending of the array to the beginning.
Okay, so let's discuss two greedy approaches for solving this question.