Climbing Stairs

NeetCode: Climbing Stairs · LeetCode: 70. Climbing Stairs · Difficulty: Easy

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

Example

Text

Input:  n = 3    Output: 3    (1+1+1, 1+2, 2+1)
Input:  n = 5    Output: 8

The last move into step n came either from step n - 1 (a 1-step) or from step n - 2 (a 2-step). So ways(n) = ways(n - 1) + ways(n - 2), with ways(0) = ways(1) = 1. This is the Fibonacci recurrence: the answer for a prefix is defined in terms of a few smaller prefixes.

Brute force: plain recursion

Translate the recurrence directly. Each solution is a method of class Solution, the form LeetCode expects, and Main calls it.

Java

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

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.climbStairs(3));
        System.out.println(solution.climbStairs(5));
        System.out.println(solution.climbStairs(0));
    }
}

Output

3
8
1

Each call spawns two more, and the same subproblems (climb_stairs(2), climb_stairs(3), ...) are recomputed over and over, so the call tree has about φ^n nodes. Time: O(2^n) (more precisely O(φ^n)). Space: O(n) for the recursion stack.

Better: memoization

There are only n + 1 distinct subproblems. Store each answer in an int array when it is first computed and reuse it. A new int array starts filled with 0, so 0 marks an empty slot.

Java

class Solution {
    private int go(int n, int[] memo) {
        if (n <= 1) {
            return 1;
        }
        if (memo[n] != 0) {
            return memo[n];
        }
        int ways = go(n - 1, memo) + go(n - 2, memo);
        memo[n] = ways;
        return ways;
    }

    public int climbStairs(int n) {
        int[] memo = new int[n + 1]; // 0 means "not computed yet"; every real answer is at least 1
        return go(n, memo);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.climbStairs(3));
        System.out.println(solution.climbStairs(5));
        System.out.println(solution.climbStairs(0));
    }
}

Output

3
8
1

Time: O(n), each subproblem is solved once. Space: O(n) for the table and the stack.

Optimal: keep only the last two values

ways(i) only needs ways(i - 1) and ways(i - 2), so build up from the bottom and keep two variables instead of a table.

Java

class Solution {
    public int climbStairs(int n) {
        int prev = 1; // ways(0)
        int cur = 1;  // ways(1)
        for (int i = 1; i < n; i++) {
            int next = prev + cur;
            prev = cur;
            cur = next;
        }
        return cur;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.climbStairs(3));
        System.out.println(solution.climbStairs(5));
        System.out.println(solution.climbStairs(0));
        System.out.println(solution.climbStairs(45));
    }
}

Output

Time: O(n). Space: O(1). A Java int holds the answer for every n up to the problem's limit of 45 (ways(45) is 1836311903, below Integer.MAX_VALUE). For n = 46 the sum would wrap silently to a negative number, because int addition does not throw on overflow.