Climbing Stairs (LeetCode 70)

Solution for Climbing Stairs in Java

Contents

• Approach 1: Base Recursion
• Approach 2: Top-down Dynamic Programming
• Approach 3: Bottom-up Dynamic Programming

There are multiple approaches to solve this problem.

Approach 1: Base Recursion

We will start from solving the base recurrence.

$f(n) = f(n-1) + f(n-2)$

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

        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

Approach 2: Top-down Dynamic Programming

class Solution {
    private final Map<Integer, Integer> hm = new HashMap<>();

    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        if (hm.containsKey(n)) {
            return hm.get(n);
        }

        final var v = climbStairs(n - 1) + climbStairs(n - 2);
        hm.put(n, v);
        return v;
    }
}

Approach 3: Bottom-up Dynamic Programming

class Solution {
    public int climbStairs(int n) {
        var f = 1;
        var s = 1;
        for (var i = 2; i <= n; i++) {
            final var t = s;
            s += f;
            f = t;
        }

        return s;
    }
}