Min Cost Climbing Stairs

Problem Statement

In this problem, you are presented with an integer array named cost, where each element cost[i] represents the expense of taking the i-th step on a staircase. After paying for a step, you have the option to either move up by one step or leap over to the subsequent second step. The challenge allows you to initiate your journey either from the first step (index 0) or from the second step (index 1). The goal is to determine the least amount of total cost required to reach just beyond the last step of the staircase, essentially climbing to the top of the floor.

Examples

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.

Constraints

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

Approach and Intuition

The approach to solve this problem effectively revolves around understanding it as a dynamic programming problem. The essence lies in breaking down the problem into smaller subproblems, solving each, and building up the answer. Here’s the step-by-step break down:

1. Initialization:

   • Create a new list dp of the same length as cost + 1, initialized to zero. This dp array will store the minimum cost to reach each step.

2. Base Cases:

   • You can start from either step 0 or step 1 without any prior cost, hence dp[0] = cost[0] and if the list length is greater than 1, then dp[1] = cost[1].

3. Recursive Relation:

   • For each subsequent step i (starting from 2), determine the minimum cost needed to get to that step by considering the cost to get to either one step or two steps behind, plus the cost of the current step. Formally, dp[i] = min(dp[i-1], dp[i-2]) + cost[i].
   • Essentially, we are looking back two steps at most since those are the only jump lengths allowed (either one step or two steps at a time).

4. Finalize the calculation:

   • After filling the dp array, the last two entries in the dp list (dp[-2] and dp[-1]) contain the costs of reaching the last step and one step beyond the last step, respectively. The answer is the minimum of these two values since you can either directly be on the last step already or get there by a previous jump.

5. Result:

   • Return the minimal value between dp[-1] and dp[-2] which gives the minimum cost to reach or exceed the last step, effectively reaching the top floor.

This solution leverages the overlapping subproblems normally found in staircase problems, where the optimal solution to reach a certain step is based on the optimal solutions of the previous steps.

Solutions

class Solution {
    public int minimumCostToClimb(int[] expenses) {
        int previous = 0;
        int beforePrevious = 0;
        for (int j = 2; j < expenses.length + 1; j++) {
            int temporary = previous;
            previous = Math.min(previous + expenses[j - 1], beforePrevious + expenses[j - 2]);
            beforePrevious = temporary;
        }
        
        return previous;
    }
}

class Solution:
    def minimumCostToClimb(self, steps: List[int]) -> int:
        step1 = step2 = 0
        for index in range(2, len(steps) + 1):
            current = step1
            step1 = min(step1 + steps[index - 1], step2 + steps[index - 2])
            step2 = current

        return step1