Problem of The Day: Climbing Stairs

5 min read 1083 words

Problem Statement

leetcode problem link

Solution [Accepted]

class Solution:
    def climbStairs(self, n: int) -> int:
        @cache
        def dp(i):
            if i == n:
                return 1
            if i > n:
                return 0
            one_step = dp(i + 1)
            two_step = dp(i + 2)
            return one_step + two_step


        return dp(0)

public class Solution {
    private Dictionary<int, int> _memo = new Dictionary<int, int>();

    public int ClimbStairs(int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            return 0;
        }

        if (_memo.ContainsKey(n))
            return _memo[n];

        _memo[n] = ClimbStairs(n - 1) + ClimbStairs(n - 2);

        return _memo[n];
    }
}

Time: O(n) Space: O(n)

Dynamic Programming [Accepted]

public class Solution {
    public int ClimbStairs(int n) {
        var dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Time: O(N) Space: O(N)

Editorial

Approach 2: Recursion with Memoization

public class Solution {
    public int ClimbStairs(int n) {
        int[] memo = new int[n + 1];
        return Climb_Stairs(0, n, memo);
    }

    public int Climb_Stairs(int i, int n, int[] memo) {
        if (i > n) {
            return 0;
        }

        if (i == n) {
            return 1;
        }

        if (memo[i] > 0) {
            return memo[i];
        }

        memo[i] = Climb_Stairs(i + 1, n, memo) + Climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

class Solution:
    def climbStairs(self, n: int) -> int:
        memo = [0] * (n + 1)
        return self.climb_Stairs(0, n, memo)

    def climb_Stairs(self, i: int, n: int, memo: List[int]) -> int:
        if i > n:
            return 0
        if i == n:
            return 1
        if memo[i] > 0:
            return memo[i]
        memo[i] = self.climb_Stairs(i + 1, n, memo) + self.climb_Stairs(
            i + 2, n, memo
        )
        return memo[i]

Approach 3: Dynamic Programming

# Python3
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        dp = [0 for _ in range(n + 1)]
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

public class Solution {
    public int ClimbStairs(int n) {
        if (n == 1) {
            return 1;
        }

        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}