Davis has s staircases in his house and he likes to climb each staircase 1,2, or 3 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 s staircases in his house, find and print the number of ways he can climb each staircase on a new lin…

davisStairCase.py

countStaircase={}

def countSteps(n):
    if n in countStaircase:
        return countStaircase[n]
    elif n==0:
        return 1
    elif n<0:
        return 0
    else:
        curCount=0
        curCount+=countSteps(n-3)
        curCount+=countSteps(n-2)
        curCount+=countSteps(n-1)
        countStaircase[n]=curCount
        return curCount

s = int(raw_input().strip())
for a0 in xrange(s):
    n = int(raw_input().strip())
    print(countSteps(n))

Davis has s staircases in his house and he likes to climb each staircase 1,2, or 3 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 s 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,s, denoting the number of staircases in his house.
Each line i of the s subsequent lines contains a single integer,n, denoting the height of staircase i.
Constraints

• 1 <= s <= 5
• 1 <= n <= 36
  Subtasks
• 1 <= n <= 20 for 50% 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
  */