PROBLEM LINK :
practice
contest
Tester: jeysree
Editorialist: danush10
PROBLEM EXPLANATION :
A Dog is running up a staircase with N steps. It can hop either 1 step, 2 steps or 3 steps at a time. Implement a method to count how many possible ways the dog can run up to the stairs. You need to return all possible number of ways.
DIFFICULTY :
Easy
CONSTRAINTS :
N≤30
PROBLEM EXPLANATION :
This list is : [1,1,1,1,1]−>[1,1,1,2]−>[1,1,2,1]−>[1,2,1,1]−>[2,1,1,1]−>[2,2,1]−>[2,1,2]−>[1,2,2]−>[1,1,3]−>[1,3,1]−>[3,1,1]−>[3,2]−>[2,3][1,1,1,1,1]−>[1,1,1,2]−>[1,1,2,1]−>[1,2,1,1]−>[2,1,1,1]−>[2,2,1]−>[2,1,2]−>[1,2,2]−>[1,1,3]−>[1,3,1]−>[3,1,1]−>[3,2]−>[2,3]. Number of steps iterated is 13. Hence the answer is 13.
Tester Solution
#include <stdio.h>
int findStep(int n)
{
if (n == 1 || n == 0)
return 1;
else if (n == 2)
return 2;
else
return findStep(n - 3) + findStep(n - 2) + findStep(n - 1);
}
int main()
{
int n = 5;
printf(“%d\n”, findStep(n));
return 0;
}