Climbing Stairs

Easy

The problem

A staircase has n steps. You climb either 1 or 2 steps at a time. Return how many different ways there are to reach the top.

Example 1
Input: n = 2
Output: 2
Either 1+1 or 2.
Example 2
Input: n = 3
Output: 3
1+1+1, 1+2 or 2+1.
Example 3
Input: n = 5
Output: 8

Limits

1 ≤ n ≤ 45

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

To reach step n you came from step n−1 or n−2. So how many ways in total?

The idea

ways(n) = ways(n−1) + ways(n−2); iterate keeping only the last two values.

Target: O(n) time, O(1) space

Go function shape

func climbStairs(n int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// ClimbStairs: ways to reach step n taking 1 or 2 steps at a time.
// Bottom-up with O(1) space: dp[i] only needs dp[i-1] and dp[i-2].
func ClimbStairs(n int) int {
	prev, cur := 1, 1 // ways to reach step 0 and step 1
	for i := 2; i <= n; i++ {
		prev, cur = cur, prev+cur
	}
	return cur
}

Read the lesson: Dynamic Programming