Staircase problem

# Staircase problem

March 8, 2023 Name
Moch Lutfi
@kaptenupi

## Problem

LeetCode 70 - Climbing Stairs [easy] (opens in a new tab)

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: 2Output: 2Explanation: There are two ways to climb to the top.--> 1 step + 1 step--> 2 steps

Example 2:

Input: 3Output: 3Explanation: 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

bruteforce.go
Output
package mainimport ( "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) } }}

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 mainimport ( "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.

## Bottom-Up DP with tabulation

package mainimport ( "testing")func Climb(n int) int { dp := make([]int, n+1) dp = 1 dp = 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.

## Memory optimization

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

package mainimport ( "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 (opens in a new tab)

Time Complexity: O(N)

Space Complexity: O(1)