A person has s staircases in their house and they like to climb each staircase 1

Question

A person has s staircases in their house and they like to climb each staircase 1, 2, or 4 steps at a time. They wonder how many ways there are to reach the top of the staircase. Given the respective heights for each of the s staircases in the house, find and print the number of ways they can climb each staircase on a new line. Please use array to store Dynamic Program table and develop the corresponding efficient algorithm in Java.

Input Format

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

Hint: Similar to the Davis' Staircase problem in Hackerrank.

This is what I have so far:

What should I put in some of the # positions?

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

public class Solution {

public static int countStaircase(int n){
int[] DPtable = new int[n];
if (n==#) {
return 1;
}
if (n==#) {
return 2;
}
if (n==#) {
return 7;
}
DPtable[#]=#;
DPtable[#]=#;
DPtable[#]=#;
for (int i=#; i<n; i++){
DPtable[i]= DPtable[i-1]+DPtable[i-2]+DPtable[i-4];
}
return DPtable[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();
System.out.println(countStaircase(n));
}
}
}

Explanation / Answer

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

public class Solution {

   public static int countStaircase(int n){
       int[] DPtable = new int[n];
       if (n==1) {
           return 1;
       }
       if (n==2) {
           return 2;
       }
       if (n==4) {
           return 7;
       }
       DPtable[0]=1;
       DPtable[1]=2;
       DPtable[4]=7;
       for (int i=5; i<n; i++){
           DPtable[i]= DPtable[i-1]+DPtable[i-2]+DPtable[i-4];
       }
       return DPtable[n-1];
   }

   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(countStaircase(n));
       }
   }
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.