def climb_stairs(n):
    if n == 1:
        return 1

    lookup_table = [0 for x in range(n + 1)]  

    lookup_table[1] = 1  
    lookup_table[2] = 2

    for i in range(3, n + 1):
        lookup_table[i] = lookup_table[i - 1] + lookup_table[i - 2] 
        
    return lookup_table[n]  

# Driver code
def main():
    inputs = [1, 4, 3, 5, 6]
    
    for i in range(len(inputs)):
        print(i + 1, ".\t Steps: ",inputs[i],"\n\n\t", \
                         " Number of ways: ", climb_stairs(inputs[i]), sep="") 
            
        print("-" * 100)

if __name__ == '__main__':
    main()