# Staircase problem

📚 3 min read Tweet this post
Section titled Problem

## Problem

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``````
Section titled Solution

## Solution

Section titled Brute%20Force

### Brute Force

``````package main

import (
"testing"
)

func Climb(n int) int {
if n < 3 {
return n
}
return Climb(n-1) + Climb(n-2)
}

func TestClimb(t *testing.T) {
tests := []struct {
input int
want  int
}{
{input: 2, want: 2},
{input: 3, want: 3},
}
for _, tt := range tests {
if got := Climb(tt.input); got != tt.want {
t.Errorf("LastIndex(%v) = %v, want %v", tt.input, got, tt.want)
}
}
}

``````
``````=== RUN   TestClimb
--- PASS: TestClimb (0.00s)
PASS
``````

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.

Ugh so slow, how to improve that? We must visualize the call stack first to be able to understand where is the problem.

``````            f(4)
+---------------+
f(3)             f(2)
+---------+       +-------+
f(2)      f(1)    f(1)    f(0)
+------+
f(1) f(0)``````

As you can see, there are a lot of overlapping sub-problem that we only calculate it once.

Section titled Top-Down%20DP%20with%20memoization

## Top-Down DP with memoization

``````package main

import (
"testing"
)

func Climb(n int) int {
dp := make([]int, n+1)

var recursive func(n int) int

recursive = func(n int) int {
if n < 3 {
return n
}

if dp[n] == 0 {
dp[n] = recursive(n-1) + recursive(n-2)
}

return dp[n]
}

return recursive(n)
}

func TestClimb(t *testing.T) {
tests := []struct {
input int
want  int
}{
{input: 2, want: 2},
{input: 3, want: 3},
}
for _, tt := range tests {
if got := Climb(tt.input); got != tt.want {
t.Errorf("LastIndex(%v) = %v, want %v", tt.input, got, tt.want)
}
}
}``````

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.

Section titled Bottom-Up%20DP%20with%20tabulation

## Bottom-Up DP with tabulation

``````package main

import (
"testing"
)

func Climb(n int) int {
dp := make([]int, n+1)
dp[0] = 1
dp[1] = 1

for i := 2; i < n+1; i++ {
dp[i] = dp[i-1] + dp[i-2]
}

return dp[n]
}

func TestClimb(t *testing.T) {
tests := []struct {
input int
want  int
}{
{input: 2, want: 2},
{input: 3, want: 3},
}
for _, tt := range tests {
if got := Climb(tt.input); got != tt.want {
t.Errorf("LastIndex(%v) = %v, want %v", tt.input, got, tt.want)
}
}
}
``````

Time Complexity: O(N)

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

Section titled Memory%20optimization

## Memory optimization

From the visualization of the recursive stack and other solution, we only required `n-1` and `n-2` to calculate `n`

``````package main

import (
"testing"
)

func Climb(n int) int {
a, b := 1, 1
for i := 0; i < n; i++ {
a, b = b, a+b
}

return a
}

func TestClimb(t *testing.T) {
tests := []struct {
input int
want  int
}{
{input: 2, want: 2},
{input: 3, want: 3},
}
for _, tt := range tests {
if got := Climb(tt.input); got != tt.want {
t.Errorf("LastIndex(%v) = %v, want %v", tt.input, got, tt.want)
}
}
}``````

Try it in playground https://go.dev/play/p/mBTiZjs2q0y

Time Complexity: O(N)

Space Complexity: O(1)

go dynamic programming