Teaching Kids Programming – Climbing the Stairs using Dynamic Programming Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

There’s a staircase with n steps, and you can climb up either 1 or 2 steps at a time. Given an integer n, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters, so each different order of steps counts as a way.

Mod the result by 10 ** 9 + 7.

Constraints
n ≤ 100,000
Example 1
Input
n = 4
Output
5
Explanation
There are 5 unique ways:
1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2

Example 2
Input
n = 1
Output
1
Explanation
There’s only one way: climb up 1 step.

Example 3
Input
n = 3
Output
3
Explanation
There are three ways: [1, 1, 1], [2, 1], and [1, 2].

Climbing the Stairs using Top-Down Dynamic Programming

If we use F(N) to represent the number of the ways to reach stair N, we know its previous possible locations could only be N-1 and N-2, and thus the Dynamic Programming Equation is:

In particular, and

Hey, as you may spot it, it is basically the Fibonacci Numbers.

We can implement the Recursion with Memoization:

1
2
3
4
5
6
7

@cache # which is introduced in Python3.9 the same as @lru_cache(maxsize=None)
def f(n):
  if n == 1:
    return 1
  if n == 2:
    return 2
  return f(n - 1) + f(n - 2)

@cache # which is introduced in Python3.9 the same as @lru_cache(maxsize=None)
def f(n):
  if n == 1:
    return 1
  if n == 2:
    return 2
  return f(n - 1) + f(n - 2)

Without the cache, the time complexity is O(2^n) exponential but with cache this brings down the complexity to O(N) as for each F(i) i belongs to [1, n], we only calculate once.

We can also home-make the cache with dictionary or hash map:

1
2
3
4
5
6
7
8
9
10

def f(n, cache = {}):
  if n == 1:
    return 1
  if n == 2:
    return 2
  if n in cache:
    return cache[n]
  val = f(n - 1) + f(n - 2)  
  cache[n] = val # put it in cache
  return val

def f(n, cache = {}):
  if n == 1:
    return 1
  if n == 2:
    return 2
  if n in cache:
    return cache[n]
  val = f(n - 1) + f(n - 2)  
  cache[n] = val # put it in cache
  return val

Using fancy yield to generate an iterator:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def solve(self, n):
        def fib():
            a = b = 1
            yield a
            yield b
            while True:
                yield (a + b)
                a, b = b, (a + b)
 
        f = fib()
        for _ in range(n):
            next(f)
        return next(f)

class Solution:
    def solve(self, n):
        def fib():
            a = b = 1
            yield a
            yield b
            while True:
                yield (a + b)
                a, b = b, (a + b)

        f = fib()
        for _ in range(n):
            next(f)
        return next(f)

Climbing the Stairs using Bottom-Up Dynamic Programming Algorithm

We can start computing F(1), F(2) … and until we reach F(N). We can do this using Bottom-Up Dynamic Programming i.e. via Iteration. You can allocate array for F[n] but we can use two variables to track only the previous two stats.

1
2
3
4
5
6

class Solution:
    def solve(self, n):
        a, b = 1, 1
        for _ in range(1, n):
            a, b = b, a + b
        return b

class Solution:
    def solve(self, n):
        a, b = 1, 1
        for _ in range(1, n):
            a, b = b, a + b
        return b

See also: How to Compute the Min Cost of Climbing Stairs via Dynamic Programming Algorithm?

–EOF (The Ultimate Computing & Technology Blog) —