concept · INFO-CS-ADS-173Climbing 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
Possible Ways
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2
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.
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