Climbing stairs

mediumRecursion20 XP

You climb a staircase of n steps, taking 1 or 2 steps at a time. Return how many different ways there are to reach the top. (Plain recursion is slow for big n — remember answers you've already worked out.)

Examples

Input: n = 2
Output: 2
Input: n = 3
Output: 3

Examples use JSON: true/false/null are True/False/None in Python.