- You are given a number n, representing the number of stairs in a staircase.
- You are on the 0th step and are required to climb to the top.
- You are given n numbers, where ith element's value represents - till how far from the step you could jump to in a single move. Y4. You are required to print the number of minimum moves in which you can reach the top of the staircase.
Climb Stairs With Minimum Moves
Sometimes it's better to leave something alone, to pause, and that's very true of programming.
~ Joyce Wheeler
Let's understand this first.
If we have:
x moves to go from a to D
y moves to go from b to D
z moves to go from c to D
Then for going from S to D the path with the minimum move will be min(x, y, z) + 1.
We will again make it into 3 states:
- Storage and Meaning:
This time also we will make an integer array but, it won't be int rather Integer.
In the case of int the default value is 0. But in the case of Integer the default value is null.
If we assign a value to an index in int it will directly be stored. But in the case of Integer it will just store the address of that integer value.If you still have doubts about the difference watch the video.
- Direction: Similar to the previous scenario, here also the subproblem "Minimum moves to go from n to n" is smaller than the subproblem "Minimum moves to go from 0 to n". Hence the direction will also be backward.
- Travel and Solve: Let's consider the array: [3, 2, 4, 2, 0, 2, 3, 1, 2, 2]. n=10;
The trivial case is that the minimum moves to go from 10 to 10 and the answer is 0.Now in the 9-th value, we take a max of two jumps. If we take a jump of 2 we will go outside the array, hence we can only take a jump of size 1. Thus dp = dp + 1 i.e. dp = 1.
If we keep doing it this way we will eventually solve the entire dp array. I will ask you to try to solve it yourself and if you face any difficulty watch the solution video.
O(n2)Here we are running to loops. Outerloop runs n times and the inner loop can run n times in the worst case. And within the inner loop, we are just adding hence we will get constant time. So it's O(n*n) = O(n2).
Here we are just using one dp array of length n+1, to store the results. Thus the space complexity will be O(n+1) = O(n)
With this, we conclude our question of Climb Stairs with Minimum Moves. Hope you have understood the problem. See you in the next problem.