# HackerRank Recursion: Davis' Staircase problem solution

In this HackerRank Recursion: Davis' Staircase Interview preparation kit problem you have Given the respective heights for each of the s staircases in his house, find and print the number of ways he can climb each staircase, module 10 power 10 + 7 on a new line.

## Problem solution in Python programming.

```#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the stepPerms function below.
def stepPerms(n):
steps = [1, 2, 3]
ways = dict()

def climb(n, steps, ways):
ret = 0
for step in steps:
if n - step == 0:
ret += 1
elif n - step > 0:
if n - step not in ways:
ways[n - step] = climb(n - step, steps, ways)
print(ways[n - step])
ret += ways[n - step]
return ret

return climb(n, steps, ways)

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

s = int(input())

for s_itr in range(s):
n = int(input())

res = stepPerms(n)

fptr.write(str(res) + '\n')

fptr.close()```

## Problem solution in Java Programming.

```import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class Solution {

public static class Matrix{
static int n;
public   Matrix(int n)
{
this.n=n;
}

static long[][] multiply(long[][] a ,long[][] b)
{
long[][] ans=new long[n][n];

for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
ans[i][j]=0;
for(int k=0;k<n;k++)
ans[i][j]+=a[i][k]*b[k][j];
}
return ans;
}
static void print(long[][] a)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
System.out.print(a[i][j]+" ");
System.out.println();
}
}
//Matrix Exponentiation
static long MatrixExpo(long[][] base ,int power )
{
// print(base);

//base cases
if(power<=0) return 0;
if(power==1) return 1;
if(power==2) return 2;
if(power==3) return 4;

power-=3;

long[][] ans=new long[n][n];

for(int i=1;i<n;i++)
for(int j=0;j<n;j++)  ans[i][j]=0;
ans[0][0]=4;ans[0][1]=2;ans[0][2]=1;

//Left-handside matrix
//4 2 1
//0 0 0
//0 0 0
while(power>0)
{
if(power%2==1)
ans=multiply(ans ,base);
power=power/2;
base=multiply(base ,base);

}
return ans[0][0];
}

}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int s = in.nextInt();
long[][] m=new long[3][3];
//1 1 0
//1 0 1
//1 0 0
m[0][0]=m[1][0]=m[2][0]=1;m[0][1]=1;m[0][2]=0;
m[1][1]=0;m[1][2]=1;m[2][1]=0;m[2][2]=0;

for(int a0 = 0; a0 < s; a0++){
int n = in.nextInt();
Matrix mat= new Matrix(3);
System.out.println(Matrix.MatrixExpo(m ,n));
}
}
}
```

### Problem solution in C++ programming.

```#include <bits/stdc++.h>
#define MOD 10000000007
using namespace std;
int dp[100001], n;

int count_paths(int i) {

if(i == 0)
return 1;
if(i < 0)
return 0;
if(dp[i] != -1)
return dp[i];
dp[i] = count_paths(i - 1) % MOD;
dp[i] = (dp[i] + count_paths(i - 2)) % MOD;
dp[i] = (dp[i] + count_paths(i - 3)) % MOD;
return dp[i];
}

int main() {

int t;
cin >> t;
assert(t >=1 and t<= 5);
for(int i = 0; i < t; i++) {
cin >> n;
assert(n >= 1 and n <= 100000);
memset(dp, -1, sizeof dp);
int ans = count_paths(n);
cout << ans << endl;
}

return 0;
}```