Redirecting to
NADOS


  Prev   Next

Climb Stairs With Variable Jumps







Don't write better error messages, write code that doesn't need them.
~ Jason C. McDonald

Climb Stairs With Variable Jumps

Dear reader, we will solve a new problem which is a slight variation of the old problem Climb Stairs. If you haven't solved that problem I would suggest you solve that first and come back later. If you already solved that problem try this problem by yourself and then see the approaches.

Important Links : Problem Link, Question Video

Problem Discussion :
  1. You are given n representing the number of stairs.
  2. You are on the 0th step and are required to climb to the top.
  3. You are given n numbers, where i-th element's value represents - till how far from the step you could jump to in a single move.
  4. You are required to print the number of different paths via which you can climb to the top.

Let's say if the value at the 1st index is 4 then it means from the 1st index you can make 1, 2, 3, 4 jumps to index 2, 3, 4, 5 respectively. Provided after the jumps you don't go out of the array. What I mean by that is if we are in the 5-th index and we can make max 3 length jumps but we can't because any jump will take us out of the array.

img

Now the question is how many different paths are there to reach n from 0.

Approach :1 (Recursion)

Although, I will expect you to come up with the recursive approach yourself because we have already covered this. But still, I will explain briefly. As always we will break down the problem into Expectation, Faith and then derive the Expectation from our Faith.

Here the expectation will be that countPath(0) will return the count of all paths from the index 0 to n.

The Faith will be that countPath(1), countPath(2) will return the count of all paths from index 1 to n and from index 2 to n. Why two functions in Faith? Because the value at 0 is 2, so it can at max take 2 jumps. So it can either reach 1 or reach 2. Now, let's derive Expectation from Faith.

If we have:

x ways to go from a to D

yways to go from b to D

z ways to go from c to D


Then for going from S to D we will have x+y+zapproaches.

img

Hence countPaths(0) = countPaths(1) + countPaths(2)

But we have to be careful about the jumps. The jumps we take should not get out of the range. Keeping these in mind I would insist you write the code yourself. If you face any difficulty you can refer to the code below.

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(); } int paths = countPaths(arr, 0, n); System.out.println(paths); scn.close(); } public static int countPaths(int[] arr, int index, int len) { if (index == len) { return 1; } int count = 0; for (int jump = 1; jump <= arr[index]; jump++) { if ((jump + index) <= len) { count += countPaths(arr, jump + index, len); } else { break; } } return count; } }
java; true";

If you draw the recursion tree, you will realize that there are many overlapping subproblems i.e we are solving the same problem again and again. So, we can memoize it. But here we will discuss the tabulation method.

Approach :2 (DP - Tabulation)

arr in consideration: [2, 3, 0, 1, 2, 3]

For DP approach we will do it in 3 steps:

  1. Storage and Meaning: We will make an array of n size and call it dp. Now, dp[i] will store the number of paths to reach n from i. For example,
    dp[0] will store the number of paths to reach n from 0.
    dp[1] will store the number of paths to reach n from 1. And so on.
  2. Direction:
    To get the direction we ask the following questions:
    1. What is the number of paths to reach 6 from 6?
    2. What is the number of paths to reach 6 from 0?
    Out of these, the 1st question is easy to answer and the answer is 1. So the direction will be from 6 -> 0
    img
  3. Travel and Solve:
    First, we will fill up the base case and start traveling in the direction we decided earlier.
    img
    Now, arr[5] = 3, hence we can make 3 jumps at max. But if we make the jump of length 3 we will reach the 8-th index which is not possible. Also, a jump of length 2 is not possible since it will go outside. So we can only make a jump of 1 and reach 6. So dp[5] = 1.
    img
    Not arr[4] = 2, hence we can make 2 jumps at max. If it takes 1 jump it will reach 5 that has a value of 1. And if it takes 2 jumps then it will reach 6 that also has a value of 1. Hence dp[4] = 1+1 = 2.
    img
    We can continue in the same manner as follows:
    img
    img
    img
    img
    Hence dp[0] = 4. i.e the total paths to reach 6 from 0 is 4.

If you faced any difficulty understanding this section you can watch the solution video.

Now you can try to code this problem in your editor. If you face any difficulty you can check the code below:

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(); } int[] dp = new int[n + 1]; dp[n] = 1; for (int i = n - 1; i >= 0; i--) { for (int reach = i + 1; reach <= Math.min(n, i + arr[i]); reach++) { dp[i] += dp[reach]; } } System.out.println(dp[0]); scn.close(); } }
java; true";

If you still face any difficulty in the code you can watch the solution video from [7:30 - 11:50]

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)

Accolite
Amazon
Author: Arnab Sen
 
Run
Id Name