Recursion: Davis' Staircase - Hacker Rank Solution

Recursion: Davis' Staircase - Hacker Rank Solution

C++

#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;
}

Java
import java.util.*;

class Solution {
    final static long _MOD = 1000000007;
    
    public static long countPathsMemoized(int numberOfSteps) {
        long[] memo = new long[numberOfSteps + 1];
        long numberOfWays = 1;
        for(int i = 1; i < numberOfSteps; i++) {
            numberOfWays += countPathsMemoized(i, memo);
        }
        return numberOfWays % _MOD;
    }
    
    public static long countPathsMemoized(int numberOfSteps, long[] memo) {
        if(numberOfSteps < 3) {
            return (numberOfSteps > 0) ? numberOfSteps : 0;
        }
        if(memo[numberOfSteps] == 0) {
            memo[numberOfSteps] = (
                                  countPathsMemoized(numberOfSteps - 1, memo)
                                + countPathsMemoized(numberOfSteps - 2, memo)
                                + countPathsMemoized(numberOfSteps - 3, memo)
                                ) % _MOD;
                                
        }
        return memo[numberOfSteps];
    }  
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numberOfStaircases = scanner.nextInt();
        while(numberOfStaircases-- > 0) {
            int numberOfSteps = scanner.nextInt();
            System.out.println(countPathsMemoized(numberOfSteps));
        }
        
        scanner.close();
    }
}