Published on

# Staircase problem

Authors

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

_5Input: 2_5Output: 2_5Explanation: There are two ways to climb to the top._5--> 1 step + 1 step_5--> 2 steps

Example 2:

_6Input: 3_6Output: 3_6Explanation: There are three ways to climb to the top._6--> 1 step + 1 step + 1 step_6--> 1 step + 2 steps_6--> 2 steps + 1 step

## Solution

### Brute Force

bruteforce.go
Output
_27package main_27_27import (_27 "testing"_27)_27_27func Climb(n int) int {_27 if n < 3 {_27 return n_27 }_27 return Climb(n-1) + Climb(n-2)_27}_27_27func TestClimb(t *testing.T) {_27 tests := []struct {_27 input int_27 want int_27 }{_27 {input: 2, want: 2},_27 {input: 3, want: 3},_27 }_27 for _, tt := range tests {_27 if got := Climb(tt.input); got != tt.want {_27 t.Errorf("LastIndex(%v) = %v, want %v", tt.input, got, tt.want)_27 }_27 }_27}

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.

_7 f(4)_7 +---------------+_7 f(3) f(2)_7 +---------+ +-------+_7 f(2) f(1) f(1) f(0)_7+------+ _7f(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

_40package main_40_40import (_40 "testing"_40)_40_40func Climb(n int) int {_40 dp := make([]int, n+1)_40_40 var recursive func(n int) int_40_40 recursive = func(n int) int {_40 if n < 3 {_40 return n_40 }_40_40 if dp[n] == 0 {_40 dp[n] = recursive(n-1) + recursive(n-2)_40 }_40_40 return dp[n]_40 }_40_40 return recursive(n)_40}_40_40func TestClimb(t *testing.T) {_40 tests := []struct {_40 input int_40 want int_40 }{_40 {input: 2, want: 2},_40 {input: 3, want: 3},_40 }_40 for _, tt := range tests {_40 if got := Climb(tt.input); got != tt.want {_40 t.Errorf("LastIndex(%v) = %v, want %v", tt.input, got, tt.want)_40 }_40 }_40}

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

_32package main_32_32import (_32 "testing"_32)_32_32func Climb(n int) int {_32 dp := make([]int, n+1)_32 dp[0] = 1_32 dp[1] = 1_32_32 for i := 2; i < n+1; i++ {_32 dp[i] = dp[i-1] + dp[i-2]_32 }_32_32 return dp[n]_32}_32_32func TestClimb(t *testing.T) {_32 tests := []struct {_32 input int_32 want int_32 }{_32 {input: 2, want: 2},_32 {input: 3, want: 3},_32 }_32 for _, tt := range tests {_32 if got := Climb(tt.input); got != tt.want {_32 t.Errorf("LastIndex(%v) = %v, want %v", tt.input, got, tt.want)_32 }_32 }_32}

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

_29package main_29_29import (_29 "testing"_29)_29_29func Climb(n int) int {_29 a, b := 1, 1_29 for i := 0; i < n; i++ {_29 a, b = b, a+b_29 }_29_29 return a_29}_29_29func TestClimb(t *testing.T) {_29 tests := []struct {_29 input int_29 want int_29 }{_29 {input: 2, want: 2},_29 {input: 3, want: 3},_29 }_29 for _, tt := range tests {_29 if got := Climb(tt.input); got != tt.want {_29 t.Errorf("LastIndex(%v) = %v, want %v", tt.input, got, tt.want)_29 }_29 }_29}

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

Time Complexity: O(N)

Space Complexity: O(1)