You climb a staircase taking 1 or 2 steps at a time. Count the different ways to reach the top of n stairs. Plain recursion is too slow for large n; remember answers you have already computed.
What to build
A counting problem that needs a memo to be fast enough.
Requirements
- Read
n. - Print the number of ways, remembering answers you have already found.
Input
One whole number n from 1 to 80.
Output
The number of ways.
Constraints
n is from 1 to 80.
Example
Input:
3
Output:
3
Why it works
The last step is either 1 stair or 2, so ways(n) is ways(n - 1) + ways(n - 2), and storing the answers removes the repeated work.
Examples
Example 1 · Input
3
Expected output
3
Example 2 · Input
5
Expected output
8
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
ways(n) = ways(n - 1) + ways(n - 2): the last move is 1 step or 2.
Hint 2
Store each answer in a dictionary, or use @lru_cache.
Solution
Show one correct solution (try it yourself first)
memo = {}
def ways(n):
if n <= 2:
return n
if n not in memo:
memo[n] = ways(n - 1) + ways(n - 2)
return memo[n]
print(ways(int(input())))