Explore Curriculum Notes Playground

Loading...

Loading Curriculum...

Loading Subject...

Loading Topic...

Loading Lesson...

Data Structures and Algorithms Dynamic Programming

Climbing Stairs

Lesson 12/97

Loading Lab...

DYNAMIC PROGRAMMING › 1D ARRAYS

Climbing Stairs

Count the number of ways to reach the top when each move can be either 1 step or 2 steps.

Time

O(N)

Space

O(1) or O(N)

Key Principle 1

The recurrence is dp[i] = dp[i - 1] + dp[i - 2].

Key Principle 2

This is essentially Fibonacci with a story attached.

Key Principle 3

It teaches counting DP, which is different from minimizing or maximizing DP.

Key Principle 4

The table can be compressed to two rolling variables.