Ways to Climb Stairs

Array Easy 4 views

Like7

You’re at the bottom of a staircase with n steps and want to be at the top. Each move covers either 1 or 2 steps. Your task in Ways to Climb Stairs is to find the total number of distinct move sequences that reach the top exactly. The order of steps matters: taking 1 then 2 is different from taking 2 then 1!

The "secret sauce" here is Iterative Accumulation (DP). To reach step i, your final move must have been either a 1-step from i-1 or a 2-step from i-2. This means the total ways to reach i is simply the sum of ways to reach those two prior positions. It's a classic pattern that solves the problem in O(n) time with minimal memory! Each pattern must add up exactly to n without overshooting. Mastering this logic lets you count billions of possible paths instantly, turning a complex combinatorial problem into a simple, professional routine for the dispatch team.

Examples

Example 1

Input

n = 3

Output

Explanation

The sequences are [1,1,1], [1,2], and [2,1].

Example 2

Input

n = 5

Output

Explanation

There are eight distinct sequences of 1s and 2s that sum to 5.

Example 3

Input

n = 1

Output

Explanation

Only one way — take a single step.

Algorithm Flow

Recommendation Algorithm Flow for Ways to Climb Stairs - Budibadu

Best Answers

java

class Solution {
    public int climb_stairs(Object n) {
        int num = (int) n;
        if (num <= 2) {
            return num;
        }
        int prev = 1;
        int curr = 2;
        for (int i = 3; i <= num; i++) {
            int next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

javascript

function climb_stairs(n) {
    if (n <= 2) {
        return n;
    }
    let prev = 1;
    let curr = 2;
    for (let i = 3; i <= n; i++) {
        const next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

php

<?php
function climb_stairs($n) {
    if ($n <= 2) {
        return $n;
    }
    $prev = 1;
    $curr = 2;
    for ($i = 3; $i <= $n; $i++) {
        $next = $prev + $curr;
        $prev = $curr;
        $curr = $next;
    }
    return $curr;
}

python

from typing import List

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    prev, curr = 1, 2
    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr
    return curr

rust

fn climb_stairs(n: i32) -> i32 {
    if n <= 2 {
        return n;
    }
    let mut prev = 1;
    let mut curr = 2;
    for _ in 3..=n {
        let next = prev + curr;
        prev = curr;
        curr = next;
    }
    curr
}

typescript

function climb_stairs(n: any): any {
    if (n <= 2) {
        return n;
    }
    let prev = 1;
    let curr = 2;
    for (let i = 3; i <= n; i++) {
        const next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.

Ways to Climb Stairs

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Array Problems

Longest Consecutive Sequence

Garden Relay Count

Lantern Stall Picks

Festival Stall Order

Studio Lighting Slots

Seaport Ferry Gate Control

Comments (0)

Join the Discussion