[LeetCode] 746. Min Cost Climbing Stairs

1. Question

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
 

2. Thoughts

1. Use DP
2. Use Memoization to calculate current position's cost (to come from -1 or -2)

3. Tips learned

4. My solution

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(2, len(cost)):
            cost[i] += min(cost[i - 1], cost[i - 2])

        return min(cost[-1], cost[-2])

284/284 cases passed (56 ms)
Your runtime beats 78.72 % of python3 submissions
Your memory usage beats 23.59 % of python3 submissions (17.6 MB)

5. AI Solution and Improvements

Your solution for finding the minimum cost to reach the top of the staircase is efficient and utilizes dynamic programming effectively. However, there are a few tweaks that can make your code more memory-efficient and slightly more Pythonic:

1. Avoid Modifying the Input List: It's generally a good practice not to modify the input directly unless specified, as this could have unintended side effects elsewhere in a larger program.

2. Use Separate Variables for State: Similar to the Tribonacci sequence optimization, you can maintain the state using two variables that track the minimum cost to reach the current and previous steps.

Here's an optimized version of your code:

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if len(cost) <= 2:
            return min(cost)

        prev, curr = cost[0], cost[1]
        for i in range(2, len(cost)):
            next_step = cost[i] + min(prev, curr)
            prev, curr = curr, next_step

        return min(prev, curr)

In this version, prev and curr store the minimum cost to reach the previous and current steps, respectively. The loop then iterates over the cost array starting from index 2, and for each step, it calculates the minimum cost to reach that step (next_step). After each iteration, prev and curr are updated for the next iteration. Finally, the function returns the minimum of prev and curr, which represents the minimum cost to reach the top of the stairs. This approach avoids modifying the input array and uses less space.