Recursion: Davis' Staircase

Recursion, if computation is repeated, memorization can be used to make it linear. Some of them, if asking summary of something, DP can usually be used to solve it.

In this post, I am providing DP solution instead of recursion, which should be easily be written with memorization as an optimization.

Davis has 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 on a new line.

Input Format

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

Constraints

• 
  
• 
  

Subtasks

• for of the maximum score.

Output Format

For each staircase, print the number of ways Davis can climb it in a new line.

Sample Input

3
1
3
7

Sample Output

1
4
44

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:
   
   1. 
      
   2. 
      
   3. 
      
   4. 
      

Thus, we print on a new line.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

public class Solution { static void numWays(int n){ //let dp[i] is num ways to reach stair i. //each dp[i] is an accumulation of ways to reach to there int dp[] = new int[n+1]; //assuming you are at nth stair, to reach there //you can step 1 from n-1th stair //or step 2 from n-2th stair or //step 3 from n-3th stair //so you have that many ways to reach to nth stair. //adding them up is the ways to reach to nth stair //dp[3]=dp[2]+dp[1]+dp[0]; /* to reach to stair 1, you have one way:dp[1]=1=dp[0] to reach to stair 2, you have: 1 from dp[0], that is 1 way,2. from dp[1], that's 1 way. to reach to stair 3, you can : 1. dp[0]->dp[3],2.dp[2]->dp[3],3. dp[1]->dp[3] whatever you use to reach dp[2] now contributes to dp[3] */ if(n==1){ System.out.println(1); }else if(n==2){ System.out.println(2); }else{ dp[0]=1;//0 is base dp[1]=1;dp[2]=dp[1]+dp[0]; for(int i=3;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; } System.out.println(dp[n]); } } 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(); numWays(n); } } }