Staircase 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

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)