✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-173

Climbing Stairs Problem

Understand how dynamic programming counts the number of distinct ways to climb a staircase when each move can cover either one or two steps.

Explanation

Overview

The Climbing Stairs Problem asks how many different ways a person can reach the top of a staircase when they can climb either one step or two steps at a time. Dynamic programming solves it by combining the number of ways to reach the two preceding positions.

Key concepts

State definition; Transition relation; Base cases; Overlapping subproblems; Optimal substructure

Variables

dp[n]: The number of distinct ways to reach step n.; n: The total number of staircase steps.; dp[n-1]: The number of ways to reach the previous step.; dp[n-2]: The number of ways to reach the step two positions earlier.

Complexity

naiveRecursion: O(2^n) time in the usual recursive implementation.; memoization: O(n) time and O(n) space.; tabulation: O(n) time and O(n) space.; spaceOptimized: O(n) time and O(1) auxiliary space.

Example

input: n = 4; possibleWays: 1 + 1 + 1 + 1; 1 + 1 + 2; output: 5; explanation: The final step can be reached from step 3 using one step or from step 2 using two steps. Therefore, the two counts are added.

Pseudocode

function climbStairs(n):
if n <= 1:
return 1
previous = 1
current = 1
for i = 2 to n:
next = previous + current
previous = current
current = next
return current

Applications

Counting movement combinations.; Path-counting problems.; Understanding recurrence relations.; Learning one-dimensional dynamic programming.

Variables

Dp[n]

The number of distinct ways to reach step n.

N

The total number of staircase steps.

Dp[n 1]

The number of ways to reach the previous step.

Dp[n 2]

The number of ways to reach the step two positions earlier.

Example or application

Input

n = 4

Possible Ways

  • 1 + 1 + 1 + 1

  • 1 + 1 + 2

  • 1 + 2 + 1

  • 2 + 1 + 1

  • 2 + 2

Output

5

Explanation

The final step can be reached from step 3 using one step or from step 2 using two steps. Therefore, the two counts are added.

Definition

The Climbing Stairs Problem asks how many different ways a person can reach the top of a staircase when they can climb either one step or two steps at a time. Dynamic programming solves it by combining the number of ways to reach the two preceding positions.

Mathematical Representation

dp[n] = dp[n - 1] + dp[n - 2], with dp[0] = 1 and dp[1] = 1.

Approaches

Recursion

Explores all possible sequences of one-step and two-step moves, but repeats many calculations.

Memoization

Stores the number of ways for each previously visited step.

Tabulation

Calculates the number of ways from the bottom of the staircase upward.

Space Optimized

Keeps only the counts for the two previous steps.

Pseudocode

function climbStairs(n):
if n <= 1:
return 1
previous = 1
current = 1
for i = 2 to n:
next = previous + current
previous = current
current = next
return current

Complexity

Naive Recursion

O(2^n) time in the usual recursive implementation.

Memoization

O(n) time and O(n) space.

Tabulation

O(n) time and O(n) space.

Space Optimized

O(n) time and O(1) auxiliary space.

Key Concepts

  • State definition

  • Transition relation

  • Base cases

  • Overlapping subproblems

  • Optimal substructure

Advantages

  • Efficiently counts possible staircase paths.

  • Provides a simple example of one-dimensional dynamic programming.

  • Can be implemented with constant auxiliary space.

  • Helps develop recurrence-relation skills.

Limitations

  • The basic recurrence assumes that only one-step and two-step moves are allowed.

  • Additional restrictions require changes to the state or transition.

  • Large staircase sizes may produce values beyond ordinary integer limits.

Applications

  • Counting movement combinations.

  • Path-counting problems.

  • Understanding recurrence relations.

  • Learning one-dimensional dynamic programming.

Related Topics

  • Fibonacci Sequence Using Dynamic Programming

  • Memoization

  • Tabulation

  • Combinatorics

Practice Question

How many distinct ways are there to climb a staircase containing five steps if each move covers one or two steps?

Practice Answer

8 distinct ways.

Learning Objectives

  • Explain the central idea and purpose of climbing stairs problem.

  • Identify the assumptions, inputs, and conditions relevant to climbing stairs problem.

  • Evaluate an application of climbing stairs problem for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Dynamic Programming Applications

Suggest a correction or source · More in Algorithms & Data Structures