Min Cost Climbing Stairs

XXX. Minimum Cost Climbing Stairs

Dynamic Programming

Array

Problem Statement:

You are given an integer array cost where cost[i] is the cost of stepping on the ith step. Once you pay the cost, you can either climb one or two steps. Return the minimum cost to reach the top of the floor. You can either start from step 0 or step 1.

Approach:

1. Use a bottom-up dynamic programming approach to calculate the minimum cost to reach each step.
2. Track the cost of the last two steps using two variables, first and second, to save space.
3. Iterate over the cost array starting from index 2. For each step, calculate the minimum cost to reach it by adding its cost to the minimum of the two previous steps.
4. At the end, return the minimum of the last two computed costs since the top can be reached from either of them.

Algorithm Intuition:

The problem can be visualized as climbing stairs with an associated cost for each step. The key observation is that to reach any step i, you can either come from step i-1 or step i-2. This dependency allows us to use dynamic programming to compute the minimum cost to reach each step while reusing previously calculated results. By tracking only the last two steps, we reduce space complexity to O(1).

Complexity:

Time Complexity: O(n), where n is the length of the cost array. We iterate through the array once.
Space Complexity: O(1), as we use only constant space to store intermediate results.

Java Implementation:

// Dynamic Programming solution to find the minimum cost to climb stairs
public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;

    // Initialize variables to track the last two costs
    int first = cost[0];
    int second = cost[1];
    int curr = 0;

    // Handle edge case where the input size is <= 2
    if (n <= 2) 
        return Math.min(first, second);

    // Calculate the cost for each step starting from index 2
    for (int i = 2; i < n; i++) {
        curr = cost[i] + Math.min(first, second); // Current cost
        first = second; // Shift first pointer
        second = curr;  // Shift second pointer
    }

    // The result is the minimum of the last two steps
    return Math.min(first, curr);
}