Leetcode – Min Cost Climbing Stairs Solution in Python

“Min Cost Climbing Stairs,” is a dynamic programming problem that allows developers to exercise their problem-solving skills. This article provides a detailed walk through for solving this problem using Python.

Problem Statement

The “Min Cost Climbing Stairs” problem (Leetcode 746) is described as follows:

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find the minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

For example, if the cost is [10, 15, 20], the minimum cost to reach the top of the stairs is 15. That’s because we can start at cost 1 (cost of 15) and then take one step to the top (for a total cost of 15).

Another example, if the cost is [1, 100, 1, 1, 1, 100, 1, 1, 100, 1], the minimum cost to reach the top of the stairs is 6. This is achieved by taking steps 0->2->3->5->6->7->9.

Approach to Solve the Problem

This problem is a classic dynamic programming problem. The main idea behind dynamic programming is to solve a complex problem by breaking it down into simpler subproblems and storing the solutions to each subproblem so as not to solve each one more than once.

The key to this problem is to realize that at each step, we can choose to climb one step or two steps, and we need to choose the one with the minimum cost. Therefore, for each step, the minimum cost to reach that step is the cost of that step plus the minimum cost of the previous step or the step before the previous step.

Here’s a Python solution for the problem:

class Solution:
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        f1 = f2 = 0
        for x in reversed(cost):
            f1, f2 = x + min(f1, f2), f1
        return min(f1, f2)

In this solution, we use two variables f1 and f2 to keep track of the minimum cost to reach the current step and the previous step, respectively. We iterate over the cost array in reverse order, and for each step, we update f1 and f2 based on the formula discussed above. Finally, we return the minimum of f1 and f2 because we can reach the top from either the last step or the second last step.

Time and Space Complexity

The time complexity of this solution is O(n), where n is the number of steps. This is because we have to iterate over all the steps once.

The space complexity is O(1), as we are using only a constant amount of space to store the cost variables.

Testing the Solution

Let’s test our solution with the example cases from Leetcode:

s = Solution()
print(s.minCostClimbingStairs([10, 15, 20]))  # Expected output: 15
print(s.minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))  # Expected output: 6

As we can see, the outputs are correct.

Conclusion

The “Min Cost Climbing Stairs” problem on LeetCode is an excellent example of a dynamic programming problem. The solution involves breaking down the problem into simpler subproblems and iteratively building up the solution. Understanding this problem and its solution can greatly aid in understanding the concept of dynamic programming.

This problem also teaches us an important lesson: not all problems require complex data structures or algorithms. Sometimes, simple variables and a well-thought-out iterative process can provide the optimal solution. Remember to consider all possible strategies when solving a problem, and don’t overcomplicate the solution.