CTCI Challange, DAY 18

Day 18

Problem Statement:- Recursion: Davis' Staircase

Solution:-

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

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        for(int a0 = 0; a0 < s; a0++){
            int n = in.nextInt();
            System.out.println(NoOfWays(n));
        }
    }
 
        private static int NoOfWays(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        return NoOfWays(n - 1) + NoOfWays(n - 2) + NoOfWays(n - 3);
    }
}

Note:-
updated on 22/8/17
Completed the problem with small trick.
I passed the calculated the values till 5,there by reducing the calculation time.

public class Stairs {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        for (int a0 = 0; a0 < s; a0++) {
            int n = in.nextInt();
            System.out.println(recur(n));
        }
    }

    public static int recur(int n) {
        if (n == 1) 
            return 1;
        if (n == 2)
            return 2;
        if (n == 3)
            return 4;
        if (n==4)
            return 7;
        if (n==5)
            return 13;
        return recur(n - 1) + 
                recur(n - 2) + recur(n - 3);
    }
}