Climbing Stairs

Why it belongs on this sheet

This is the cleanest way to introduce one-dimensional DP without too much setup.

Pattern

Ways to reach current step

Approach

The number of ways to reach step i is the sum of ways to reach i - 1 and i - 2. That recurrence is enough.

Java solution

class Solution {
  public int climbStairs(int n) {
    if (n <= 2) {
      return n;
    }

    int first = 1;
    int second = 2;

    for (int step = 3; step <= n; step++) {
      int current = first + second;
      first = second;
      second = current;
    }

    return second;
  }
}

Complexity

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

Interview note

This is Fibonacci in disguise, but say the state meaning instead of only naming the sequence.