70. Climbing Stairs

easy dynamic-programming

Number of distinct ways to climb n stairs taking 1 or 2 steps.

You are climbing a staircase. It takes n steps to reach the top. Each time you can climb 1 or 2 steps. How many distinct ways?

Approach

Classic DP: dp[i] = dp[i-1] + dp[i-2] (Fibonacci pattern) — O(n) time, O(1) space.

Solutions

Ruby

def climb_stairs(n)
  return n if n <= 2
  a, b = 1, 2
  (3..n).each { a, b = b, a + b }
  b
end

Python

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

Go

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    a, b := 1, 2
    for i := 3; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

TypeScript

function climbStairs(n: number): number {
    if (n <= 2) return n;
    let a = 1, b = 2;
    for (let i = 3; i <= n; i++) {
        [a, b] = [b, a + b];
    }
    return b;
}

Elixir

defmodule Solution do
  def climb_stairs(n) when n <= 2, do: n
  def climb_stairs(n), do: do_climb(3, n, 1, 2)

  defp do_climb(i, n, a, b) when i > n, do: b
  defp do_climb(i, n, a, b), do: do_climb(i + 1, n, b, a + b)
end