Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Climbing Stairs

LeetCode #70Easy
ways(i) = ways(i−1) + ways(i−2) · Fibonacci

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

Asked atAmazonAdobeApple
step 1 / 11
·
·
·
·
·
·
Brute force · recursion
▸
1ways(i):
2    if i <= 1: return 1
3    return ways(i−1) + ways(i−2)   // recomputes!
state
  • n5
  • recurrenceways(i) = ways(i−1) + ways(i−2)

line 1From step n you arrived either by a 1-step (from n−1) or a 2-step (from n−2). So ways(n) = ways(n−1) + ways(n−2), with ways(0) = ways(1) = 1. The obvious code is direct recursion.