Dear readers, this is a very similar question to that of the previous one, except that instead of counting all the paths, we want the path with minimum moves.
Important Links : Problem Link, Question Video, Solution Video
Prev Next
Climb Stairs With Minimum Moves
Sometimes it's better to leave something alone, to pause, and that's very true of programming.
~ Joyce Wheeler
Climb Stairs With Minimum Moves
Problem Discussion :
- 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.
Approach : (DP)
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.Now for the meaning part. dp[i] will store the minimum number of moves needed to move from i to n. - 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[9] = dp[10] + 1 i.e. dp[9] = 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.
import java.io.*;
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scn.nextInt();
}
Integer[] dp = new Integer[n + 1];
dp[n] = 0;
for (int i = n - 1; i >= 0; i--) {
if (arr[i] == 0)
continue;
int min = Integer.MAX_VALUE;
for (int j = 1; j <= arr[i] && i + j < dp.length; j++) {
if (dp[i + j] != null) {
min = Math.min(min, dp[i + j]);
}
}
if (min != Integer.MAX_VALUE)
dp[i] = min + 1;
}
System.out.println(dp[0]);
scn.close();
}
}
java;
true";
Analysis
Time Complexity :
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).SPACE COMPLEXITY :
O(n)
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.
