climbing stairs

Understanding the Problem

To solve the problem of climbing stairs, you can use a technique called dynamic programming. Dynamic programming is a method for solving problems by breaking them down into smaller subproblems and storing the solutions to these subproblems so that they can be reused.

In the case of climbing stairs, the subproblems are the number of ways to climb a staircase with n steps, where n is a positive integer. The base cases are n = 0, n = 1, and n = 2, as there is only one way to climb a staircase with 0 steps, 1 step, or 2 steps, respectively.

For any other value of n, you can climb the staircase by either climbing one step and then solving the subproblem for n-1 steps or by climbing two steps and then solving the subproblem for n-2 steps.

The total number of ways to climb the staircase is the sum of the number of ways to climb the staircase by climbing one step and the number of ways to climb the staircase by climbing two steps.

Solution: Recursive Function

Here's a brute-force solution to this problem.

class Solution:

        def climb_stairs(self, n):
		
		        if n ==1 or n ==0 or n== 2:
			        return n

		        count =self.climb_stairs(n-1) + self.climb_stairs(n-2)
		        return count

This method takes the number of steps n as input and returns the number of ways to climb the staircase. It first checks if n is a base case. If it is, then the function returns the number of ways to climb the staircase with n steps.

Otherwise, the method recursively calls itself to solve the subproblems for n-1 and n-2 steps and then returns the sum of the results.

Time and space Complexity

The time complexity of the recursive solution for climbing stairs is O(2^n), where n is the number of steps in the staircase. This is because the solution involves making a recursive call for each subproblem, and there are 2^n subproblems.

The space complexity of the solution is O(n), where n is the number of steps in the staircase. This is because the solution requires a memoization table with n entries.

Solution: Top-Down Dynamic Programming

In a top-down dynamic programming solution, you can use memoization to store the results of subproblems. As a result, you avoid redundant calculations.

class Solution:

    def climb_stairs(self, n: int) -> int:
        memo = {}

        def climb_stairs_helper(k):
            if k == 0 or k == 1 or k == 2:
                return k

            # Check if the result for k is already memoized
            if k in memo:
                return memo[k]

            # Calculate and memoize the result for k
            count = climb_stairs_helper(k - 1) + climb_stairs_helper(k - 2)
            memo[k] = count

            return count

        return climb_stairs_helper(n)

Thought Process

Here's how I arrived at this solution.

Original Recursive Solution

The initial solution is a straightforward recursive approach where the number of ways to climb the stairs at the step n is the sum of the ways to climb the stairs at steps n-1 and n-2.

Identifying Redundancy

In the original recursive solution, there's a lot of redundant computation. For example, when calculating climb_stairs(n), it recalculates climb_stairs(n-1) and climb_stairs(n-2), even if those values have been computed before.

Memoization

The idea behind top-down dynamic programming is to store the results of subproblems in a data structure (in this case, a dictionary called, memo).

Before performing a recursive call, we check if the result for a specific input has already been computed and stored in the memo. If yes, we use the stored result instead of recalculating.

Code Explanation

class Solution:

        def bottom_up(self, n):
		
		        dp ={0:0,1:1,2:2}
		        for i in range(3, n+1):
			        dp[i] = dp[i-1] + dp[i-2]
		        return dp[n]