Climb Stairs

1. You are given a number n, representing the number of stairs in a staircase.

2. You are on the 0th step and are required to climb to the top.

3. In one move, you are allowed to climb 1, 2 or 3 stairs.

4. You are required to print the number of different paths via which you can climb to the top.

Input Format

A number n

Output Format

A number representing the number of ways to climb the stairs from 0 to top.

Constraints

0 <= n <= 20

Sample Input

4

Sample Output

7

Solution:

import java.io.*;

import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {

        // write your code here

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        System.out.println(WaysUp(n));

    }

    public static int WaysUp(int n){

        if(n == 0)  return 0;

        else if(n<0)    return -1;

        int[] A = new int[n+1];

        A[0] = 1;

        for(int i=1;i<=n;i++){

            A[i] = A[i-1];

            if(i>= 2)

                A[i] += A[i-2];

            if(i>=3)

                A[i] += A[i-3];

        }

        return A[n];

    }

}