Dynamic programming is the art of solving a big problem by combining answers to smaller overlapping subproblems, and remembering each answer so you never recompute it.
Your first task is the classic stair-climbing count. You can climb either 1 or 2 stairs at a time. How many distinct ways can you reach the top of a staircase with n stairs?
The number of ways to reach stair n equals the ways to reach stair n-1 (then step 1) plus the ways to reach stair n-2 (then step 2). That is a Fibonacci-style recurrence.
Implement climb_stairs(n) using memoization: a recursive helper that caches each computed result in a dictionary so repeated subproblems are solved only once.
Base cases: there is exactly 1 way to stand at the bottom (n equals 0), and 0 ways for a negative number of stairs.
Examples:
def climb_stairs(n):
"""Number of ways to climb n stairs taking 1 or 2 steps, using memoization."""
# TODO: build a recursive helper with a memo dictionary.
# Base cases: 0 stairs -> 1 way, negative stairs -> 0 ways.
# Otherwise ways(k) = ways(k - 1) + ways(k - 2).
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
Dynamic programming is the art of solving a big problem by combining answers to smaller overlapping subproblems, and remembering each answer so you never recompute it.
Your first task is the classic stair-climbing count. You can climb either 1 or 2 stairs at a time. How many distinct ways can you reach the top of a staircase with n stairs?
The number of ways to reach stair n equals the ways to reach stair n-1 (then step 1) plus the ways to reach stair n-2 (then step 2). That is a Fibonacci-style recurrence.
Implement climb_stairs(n) using memoization: a recursive helper that caches each computed result in a dictionary so repeated subproblems are solved only once.
Base cases: there is exactly 1 way to stand at the bottom (n equals 0), and 0 ways for a negative number of stairs.
Examples:
Press Run Tests or ⌘↩ to check your solution.