Recursion: Davis' Staircase HackerRank Solution

Recursion: Davis' Staircase HackerRank Solution
Source : https://www.hackerrank.com/challenges/ctci-recursive-staircase

Davis has a number of staircases in his house and he likes to climb each staircase , , or steps at a time. Being a very precocious child, he wonders how many ways there are to reach the top of the staircase.

Given the respective heights for each of the staircases in his house, find and print the number of ways he can climb each staircase, module on a new line.

For example, there is staircase in the house that is steps high. Davis can step on the following sequences of steps:

1 1 1 1 11 1 1 21 1 2 1 1 2 1 12 1 1 11 2 22 2 12 1 21 1 31 3 13 1 12 33 2

There are possible ways he can take these steps.

Function Description

Complete the stepPerms function in the editor below. It should recursively calculate and return the integer number of ways Davis can climb the staircase, modulo 10000000007.

stepPerms has the following parameter(s):

• n: an integer, the number of stairs in the staircase

Input Format

The first line contains a single integer, , the number of staircases in his house.
Each of the following lines contains a single integer, , the height of staircase .

Constraints

Subtasks

• for of the maximum score.

Output Format

For each staircase, return the number of ways Davis can climb it as an integer.

Sample Input

3137

Sample Output

1444

Explanation

Let's calculate the number of ways of climbing the first two of the Davis' staircases:

1. The first staircase only has step, so there is only one way for him to climb it (i.e., by jumping step). Thus, we print on a new line.
2. The second staircase has steps and he can climb it in any of the four following ways:
   

Thus, we print on a new line.

Source : https://www.hackerrank.com/challenges/ctci-recursive-staircase

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	import java.util.HashMap;
	// Recursive solution using dynamic programming
	// Time Complexity: O(n)
	// Space Complexity: O(n)
	// Can alternatively be solved in O(1) space (per testcase) by using iteration instead of recursion
	public class Solution {
	private static HashMap<Integer, Integer> cache = new HashMap();
	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int testcases = scan.nextInt();
	cache.put(0, 1); // base case
	while (testcases-- > 0) {
	int n = scan.nextInt();
	System.out.println(staircase(n));
	}
	scan.close();
	}
	private static int staircase(int n) {
	if (n < 0) {
	return 0;
	}
	if (cache.containsKey(n)) {
	return cache.get(n);
	}
	int ways = staircase(n - 1) + staircase(n - 2) + staircase(n - 3);
	cache.put(n, ways);
	return ways;
	}
	}