Coding Patterns: Staircase (DP)

9 minute read

In Coding Patterns series, we will try to recognize common patterns underlying behind each algorithm question, using real examples from Leetcode.

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets, Modified Binary Search, Top K Numbers, K-way Merge, 0/1 Knapsack, Topological Sort and Bitwise XOR patterns and today, we will introduce Staircase pattern which is very useful to solve Dynamic Programming problems involving minimum/maximum steps, jumps, stairs, fibonacci numbers etc. to reach a target.

If you need to refresh your knowledge of Dynamic Programming, you may want to check the Fibonacci Number Problem before diving into more advanced problems.

Problem: Climbing Stairs

LeetCode 70 - Climbing Stairs [easy]

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note:

Given n will be a positive integer.

Example 1:

Input: 2

Output: 2

Explanation: There are two ways to climb to the top.

  • 1 step + 1 step
  • 2 steps

Example 2:

Input: 3

Output: 3

Explanation: There are three ways to climb to the top.

  • 1 step + 1 step + 1 step
  • 1 step + 2 steps
  • 2 steps + 1 step

Brute Force Solution

At every step, we have two options: either climb 1 step or 2 steps.

class Solution:
    def climbStairs(self, n: int) -> int:
        # we don't take any steps, so there is only 1 way
        if n == 0:
            return 0
        # we can take one step to reach the end, and this is the only way
        if n == 1:
            return 1
        # we can take one step twice or take two steps to reach the end
        if n == 2:
            return 2

        # if we take one step, we are left with "n - 1" steps
        take1step = self.climbStairs(n - 1)
        # if we take two steps, we are left with "n - 2" steps
        take2steps = self.climbStairs(n - 2)

        return take1step + take2steps

Time Complexity: O(2N) because we are making 2 recursive calls in the same function.

Space Complexity: O(N) which is used to store the recursion stack.

But can we do better? To be able to understand this, lets visualize the recursion stack.

Climbing Stairs

We can clearly see from colors that there are lots of overlapping sub-problems that we don’t need to calculate them again and again.

Top-down Dynamic Programming with Memoization

We can use an array to store already solved sub-problems.

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0 for x in range(n+1)]
        return self.climbStairs_recursive(dp, n)
    
    def climbStairs_recursive(self, dp, n):
        # we don't take any steps, so there is only 1 way
        if n == 0:
            return 0
        # we can take one step to reach the end, and this is the only way
        if n == 1:
            return 1
        # we can take one step twice or take two steps to reach the end
        if n == 2:
            return 2
        
        if dp[n] == 0:
            # if we take one step, we are left with "n - 1" steps
            take1step = self.climbStairs_recursive(dp, n - 1)
            # if we take two steps, we are left with "n - 2" steps
            take2steps = self.climbStairs_recursive(dp, n - 2)
            
            dp[n] = take1step + take2steps
            
        return dp[n]

Time Complexity: O(N) because memoization array dp[n+1] stores the results of all sub-problems. We can conclude that we will not have more than n + 1 sub-problems.

Space Complexity: O(N) which is used to store the recursion stack.

Bottom-up Dynamic Programming with Tabulation

Let’s try to populate our dp[] array in a bottom-up fashion. As we see from the recursion stack visualization, each climbStairs(n) call is the sum of the two previous calls.

We can use this fact while populating our dp[] array.

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0 for x in range(n+1)]
        dp[0] = 1
        dp[1] = 1

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

Time Complexity: O(N)

Space Complexity: O(N) which is used to store the recursion stack.

Memory Optimization

As we can see from the visualization of the recursive stack and other solutions, to be able to calculate the n, you need the value of last two combinations: n-1 and n-2.

These two values are enough and we don’t need to store all other past combinations.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 0:
            return 0
        if n == 1:
            return 1
        if n == 2:
            return 2

        first = 1  # how many step possibilities there are with 1 stairs
        second = 2  # how many step possibilities there are with 2 stairs
        third = 0

        for _ in range(2, n):
            third = first + second
            first = second  # walk up first to second
            second = third  # walk up second to third
        return third

OR more shortly;

class Solution:
    def climbStairs(self, n: int) -> int:
        a = b = 1
        for _ in range(n):
            a, b = b, a + b
        return a

Time Complexity: O(N)

Space Complexity: O(1)

How to identify?

Staircase pattern is very useful to solve Dynamic Programming problems involving minimum/maximum steps, jumps, stairs, fibonacci numbers etc. to reach a target.

Similar LeetCode Problems