# Coding Patterns: Staircase (DP)

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(2 ^{N})** 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.

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.