Climbing Stairs

Back to problems

Leetcode

Easy

Dynamic Programming

Combinatorics

Recursion

Climbing Stairs

Count the number of distinct ways to reach the top of a staircase when each move can be 1 or 2 steps.

Acceptance 61%

Start Practice

Problem Statement

You are given a staircase with n steps. You start on step 0 and want to reach step n.

At each move, you may climb either 1 step or 2 steps.

Return the number of distinct ways to reach the top.

A way is defined by the sequence of moves you make, not just the final position.

Input Format

An integer n representing the total number of steps.

Output Format

Return an integer: the number of distinct ways to reach step n.

Constraints

$1 \le n$
Use 64-bit integer arithmetic if needed.
Count different move sequences as different ways.

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 2

Output

Explanation

The two ways are: 1 + 1 and 2.

Example 2

Input

n = 3

Output

Explanation

The three ways are: 1 + 1 + 1, 1 + 2, and 2 + 1.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress