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**

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

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**

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.**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(n ^{2})**

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.