Climbing Stairs

The problem

You stand on the ground at the foot of a staircase of n steps. Each move takes you up 1 step or 2 steps, and you must land exactly on step n, the top. Return the number of different ways to do that. Two ways are different when their moves differ in any place, so a move of 1 followed by a move of 2 is not the same way as a move of 2 followed by a move of 1. When n is 0 you are already at the top, and that counts as one way.

What to write

function solve(n: number): number

Input
n = 2

Output
2

Input
n = 3

Output
3

Constraints

Integer n from 0 to 40.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   n can be as large as 40, and 40 steps can be climbed in 165,580,141 ways. That is a lot to walk through one way at a time. Notice what is asked: how many ways there are, not what they are.

2. Hint 2: Ask a smaller question

   Write out every way to climb 4 steps. There are 5. Now look at the last move of each one. How many end with a move of 1, and how many end with a move of 2? Where have you seen those two numbers before?

3. Hint 3: Name the pattern

   The answer for a step is built from the answers for the two steps below it: every way ends with a move of 1 from the step below or a move of 2 from two below, so the counts add. Solving small versions of a question first and reusing their answers is dynamic programming, here one-dimensional: one answer per step. Read the lesson on one-dimensional dynamic programming.

4. Hint 4: State the invariant

   Before you work out step i, you hold the number of ways to reach step i - 2 and step i - 1. Their sum is the number of ways to reach step i. Counts older than those two are never needed again.

5. Hint 5: Sketch the pseudocode

   previous = 1 and current = 1: the counts for step 0, which is the ground, and for step 1. For each step from 2 up to n: ways = previous + current, then previous = current, then current = ways. Return current.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

A path to step n ends with a one-step or two-step move. Add the counts for the preceding two steps and retain only those two counts.

The slow way

Write out every sequence of moves and count them. It is correct, but the number of ways grows fast: 89 for 10 steps, 10,946 for 20 and 165,580,141 for 40. Going through them one at a time takes at least that many rounds, and the question asks only how many ways there are, not what they are.

The insight

Group the ways to reach a step by their last move: a move of 1 from the step below, or a move of 2 from two below. So the count for a step is the sum of those two lower steps' counts. Each of them answers the same question about a shorter staircase. A smaller question like that is called a subproblem, and its answer can be kept and reused.

Step by step

1. Start with 1 way for step 0 and 1 way for step 1. Step 0 is the ground you start on: 1 way, making no move. Step 1 has 1 way, a single move of 1. Neither has two steps below it, so neither can be the sum of two lower counts.
2. Work out each step from 2 up to n, lowest first. Going upward, the two counts a step needs are ready when you reach it. Going downward from n and storing nothing repeats the same questions: for n = 10, the count for step 2 is worked out 34 times.
3. Add the counts of the two steps below it. Every way to this step ends with a move of 1 from the step below or a move of 2 from two below. No way is in both groups, so the sum counts each way once.
4. Keep only the two newest counts. The next step needs the counts of the two steps right below it and nothing older. So of the three counts now known, the oldest one is dropped.
5. Return the newest count, the answer for n. After the last round the newest count belongs to step n. When n is 0 or 1 the loop never runs, and the starting count of 1 is the right answer for both.

The same numbered steps are the comments in each solution.

function solve(n) {
  // 1. Start with 1 way for step 0 and 1 way for step 1
  let previous = 1;
  let current = 1;
  // 2. Work out each step from 2 up to n, lowest first
  for (let step = 2; step <= n; step++) {
    // 3. Add the counts of the two steps below it
    const ways = previous + current;
    // 4. Keep only the two newest counts
    previous = current;
    current = ways;
  }
  // 5. Return the newest count, the answer for n
  return current;
}

function solve(n: number): number {
  // 1. Start with 1 way for step 0 and 1 way for step 1
  let previous = 1;
  let current = 1;
  // 2. Work out each step from 2 up to n, lowest first
  for (let step = 2; step <= n; step++) {
    // 3. Add the counts of the two steps below it
    const ways = previous + current;
    // 4. Keep only the two newest counts
    previous = current;
    current = ways;
  }
  // 5. Return the newest count, the answer for n
  return current;
}

def solve(n):
    # 1. Start with 1 way for step 0 and 1 way for step 1
    previous = 1
    current = 1
    # 2. Work out each step from 2 up to n, lowest first
    for step in range(2, n + 1):
        # 3. Add the counts of the two steps below it
        ways = previous + current
        # 4. Keep only the two newest counts
        previous = current
        current = ways
    # 5. Return the newest count, the answer for n
    return current

Example 2, traced

Input
n = 3

Output
3

Why it works

Every count is built from two correct counts by a rule that misses no way and counts none twice, starting from two counts that are known. So each count is right, up to step n. Each one is also worked out only once and then reused. Solving small subproblems first and reusing their answers like this is called dynamic programming. One-dimensional means one answer per step, in a single row.

Time and space

Time O(n), extra space O(1). The loop runs once for each step from 2 to n and does one addition per round, so the time is O(n). However large n is, only two counts are kept, so the extra space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Work out the sum before you overwrite either count. If you first move the newer count into the older variable and then add, the newer count is added to itself and the counts double: 3 steps give 4.
• Step 0 counts as 1 way: making no move. Start that count at 0 and a staircase of 2 steps comes out as 1 way instead of 2. For the same reason the answer for n = 0 is 1.
• The loop starts at step 2, because steps 0 and 1 already have their counts. Starting it at step 1 runs one round too many and answers 2 for a single step.

Pattern

One-dimensional dynamic programming.

Keep going