## 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
```

## Solution

### 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
```

See https://go.dev/play/p/tPlQuYwe8bp

**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.

## 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)
}
}
}
```

See https://go.dev/play/p/1BlZ6_GF_AI

**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 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)
}
}
}
```

See https://go.dev/play/p/wEPgFxASeUn

**Time Complexity**: **O(N)**

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

## 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)**