Climbing Stairs

Problem

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. Return the number of distinct ways to reach the top.

Approach

Fibonacci variant. The number of ways to reach step i equals the sum of ways to reach step i-1 (take 1 step) and step i-2 (take 2 steps). Use two rolling variables instead of an array.

When to Use

Counting paths / Fibonacci family — "how many ways to reach step N", "count distinct paths with step choices". Rolling-variable DP when each state depends on a fixed number of previous states.

Complexity

Time	O(n)
Space	O(1)

Implementation

SolutionTestsChallenge

climbing_stairs

Climbing Stairs — ways to climb n stairs taking 1 or 2 steps.

Problem

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. Return the number of distinct ways to reach the top.

Approach

Fibonacci variant. The number of ways to reach step i equals the sum of ways to reach step i-1 (take 1 step) and step i-2 (take 2 steps). Use two rolling variables instead of an array.

When to use

Counting paths / Fibonacci family — "how many ways to reach step N", "count distinct paths with step choices". Rolling-variable DP when each state depends on a fixed number of previous states.

Complexity

Time: O(n) Space: O(1)

climb_stairs

climb_stairs(n: int) -> int

Return the number of distinct ways to climb n stairs.

climb_stairs(1) 1 climb_stairs(5) 8

Source code in src/algo/dp/climbing_stairs.py

def climb_stairs(n: int) -> int:
    """Return the number of distinct ways to climb *n* stairs.

    >>> climb_stairs(1)
    1
    >>> climb_stairs(5)
    8
    """
    if n < 0:
        msg = f"n must be non-negative, got {n}"
        raise ValueError(msg)
    if n <= 1:
        return 1

    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

tests/dp/test_climbing_stairs.py

"""Tests for climbing stairs."""

import pytest
from hypothesis import given
from hypothesis import strategies as st

from algo.dp.climbing_stairs import climb_stairs


class TestClimbStairs:
    def test_one_step(self) -> None:
        assert climb_stairs(1) == 1

    def test_two_steps(self) -> None:
        assert climb_stairs(2) == 2

    def test_five_steps(self) -> None:
        assert climb_stairs(5) == 8

    def test_zero_steps(self) -> None:
        assert climb_stairs(0) == 1

    def test_negative_raises(self) -> None:
        with pytest.raises(ValueError):
            climb_stairs(-1)

    @given(n=st.integers(min_value=2, max_value=30))
    def test_fibonacci_recurrence(self, n: int) -> None:
        assert climb_stairs(n) == climb_stairs(n - 1) + climb_stairs(n - 2)

Implement it yourself

Run: just challenge dp climbing_stairs

Then implement the functions to make all tests pass. Use just study dp for watch mode.

Reveal Solution

climbing_stairs

Climbing Stairs — ways to climb n stairs taking 1 or 2 steps.

Problem

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. Return the number of distinct ways to reach the top.

Approach

Fibonacci variant. The number of ways to reach step i equals the sum of ways to reach step i-1 (take 1 step) and step i-2 (take 2 steps). Use two rolling variables instead of an array.

When to use

Counting paths / Fibonacci family — "how many ways to reach step N", "count distinct paths with step choices". Rolling-variable DP when each state depends on a fixed number of previous states.

Complexity

Time: O(n) Space: O(1)

climb_stairs

climb_stairs(n: int) -> int

Return the number of distinct ways to climb n stairs.

climb_stairs(1) 1 climb_stairs(5) 8

Source code in src/algo/dp/climbing_stairs.py

def climb_stairs(n: int) -> int:
    """Return the number of distinct ways to climb *n* stairs.

    >>> climb_stairs(1)
    1
    >>> climb_stairs(5)
    8
    """
    if n < 0:
        msg = f"n must be non-negative, got {n}"
        raise ValueError(msg)
    if n <= 1:
        return 1

    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1