A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.
Input : 4
Output : 7
Input : 3
Output : 4
Solution
def countways(n) :
res = [0] * (n + 1)
res[0] = 1
res[1] = 1
res[2] = 2
for i in range(3, n + 1) :
res[i] = res[i - 1] + res[i - 2] + res[i - 3]
return res[n]
n = int(input())
print(countways(n)) 
What is the need of res statement
I need explanation of that program
This was a recursion problem. But recursion took time, so dynamic programming was applied using the res named list. All the results were calculated by the formula and stored for later use. So that again and again already calculated values need not be calculated again
/************************************************************************************************************************
The question is twisted,but it just wants us to find a fibbonaci series, but instead
of taking last two digits, we will have to take last three digits.
proof:
[LET THE NUMBER OF STAIRS BE NEGATIVE]
because if the no. of strairs is negative, the kid can’t climb it
–hence return 0;
[LET THE NUMBER OF STAIRS BE 0]
(zero)
if the number of stairs is 0, the kid cannot climb, but there is at least one floor.
–hence return 1
[LET THE NUMBER OF STAIRS BE 1]
(One)
if the number of strairs is 1, the kid can only climb it in one way
i.e just hop on one time
–hence return 1
[LET THE NUMBER OF STAIRS BE 2]
(TWO)
if the number of stairs is 2, the kid can climb it in [(1,1) steps 0r a single 2 steps]
i.e in 2 possible ways.
can you see a pattern here? no? then lets go to the next step.
–hence return 2
[LET THE NUMBER OF STAIRS BE 3]
(THREE)
possible combination{(1,1,1);(1,1,2);(2,1,1);(3)}, I.e there are 4 combinations.Can you see
the pattern? Ok, I’ll show it you.
three= combination in 2(2)+ combinations in 1(1)+ combination in 0(1)=2+1+1=4;
— hence return 4
BOOM!!
// three=combination in two(2)+ combination in one(1)+ combination in zero(1)=4 BIG BOOM!!!!
// four= combination in three(4)+ combination in two(2)+combination in one(1)=7 SLOW!!!! CLAPS!!
**************************************************************************************************************************/
import java.io.*;
public class Main
{
public static void main(String[] args)throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int input=Integer.parseInt(br.readLine());
int a=1; // for 0 steps
int b=1; // for 1 step
int c=2; // for 2 steps
int d=0;
if(input==1 || input ==2){System.out.print(input);}
else{
for(int i=3;i<=input;i++)
{
d=c+b+a;
a=b;
b=c;
c=d;
}