Leetcode: Climb Stairs

Climbing Stairs | LeetCode OJ

This is one of the most basic dynamic programming problems. The trick is to use computation from subproblems to find the result while storing results of each subproblem.

So to find the result of n steps we can simply add the results of n-1 steps and n-2 steps as these are the only 2 ways one can reach n steps. So we start by finding the result for 1 step, 2 steps, 3 steps and so on.

1. Start with results of 1 step and 2 steps
2. Add them to get result for 3 steps
3. Keep adding previous 2 results to get the next result until you reach n

Remark:

1. O(n) time complexity for using the for loop
2. O(n) space complexity for storing the results of all the n steps
3. We can optimize the space complexity by keeping track of only the last 2 values.
4. All solutions where result for n can be expressed in terms of results of n-i (i ranging from n-1 to 0) can be solved using this approach. For example, the Fibonacci series f(n) = f(n-1)+f(n-2)

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = {1: 2, 0: 1}
        for i in range(2, n):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n - 1]
    def climbStairs(self, n):
        a, b = 1, 1
        for i in range(1, n):
            a, b = b, a + b
        return b