Min Cost Climbing Stairs

#include <bits/stdc++.h> // Includes common standard libraries like iostream, vector, algorithm (for min).
using namespace std;     // Use the standard namespace.

// 1. Recursive Approach (Brute Force)
// Calculates the minimum cost to reach stair 'i'.
// Time Complexity: O(2^N) - Exponential, due to repeated calculations.
// Space Complexity: O(N) - Due to recursion stack depth.
// 'stairs': Vector containing costs for each stair.
// 'i': Current stair index being considered.
int minCostRec(vector<int> &stairs, int i) { // Renamed for clarity in main
    // Base Case 1: If index is less than 0, it means we are before the stairs. Cost is 0.
    if(i < 0) {
        return 0;
    }
    // Base Case 2: If index is 0 or 1, the cost to reach this stair is just its own cost.
    // (Since we can start from 0 or 1, and assume we've "arrived" there).
    if(i <= 1) {
        return stairs[i];
    }

    // Recursive step: To reach stair 'i', we can come from (i-1) or (i-2).
    // The cost is stairs[i] + minimum cost to reach either (i-1) or (i-2).
    int cost_from_prev1 = minCostRec(stairs, i-1); // Cost if we came from stair (i-1)
    int cost_from_prev2 = minCostRec(stairs, i-2); // Cost if we came from stair (i-2)

    return stairs[i] + min(cost_from_prev1, cost_from_prev2);
}

// 2. Dynamic Programming - Top-Down Approach (Recursion + Memoization)
// Optimizes the recursive solution by storing computed results in 'dp' table.
// Time Complexity: O(N) - Each subproblem is computed once.
// Space Complexity: O(N) for 'dp' vector + O(N) for recursion stack = O(N) total.
// 'stairs': Vector containing costs.
// 'i': Current stair index.
// 'dp': Memoization table, initialized with 0 (or -1) indicating not computed.
int minCostMemo(vector<int> &stairs, int i, vector<int> &dp) { // Renamed for clarity
    if(i < 0) { // Base Case 1
        return 0;
    }
    if(i <= 1) { // Base Case 2
        return stairs[i];
    }

    // If the result for 'i' is already computed, return it from dp table.
    if(dp[i] != 0) return dp[i]; // Assuming 0 is not a valid cost, or use -1.

    // Compute the result and store it in dp table before returning.
    dp[i] = stairs[i] + min(minCostMemo(stairs, i-1, dp), minCostMemo(stairs, i-2, dp));

    return dp[i];
}

// 3. Dynamic Programming - Bottom-Up Approach (Tabulation)
// Builds the solution iteratively from base cases up to 'n-1'.
// Time Complexity: O(N) - Single loop.
// Space Complexity: O(N) - For the 'dp' vector.
// 'stairs': Vector containing costs.
int minCostTab(vector<int> &stairs) { // Renamed for clarity
    int n = stairs.size();

    // Handle edge cases for n (number of stairs)
    if (n == 0) return 0; // No stairs, no cost.
    if (n == 1) return stairs[0]; // Only one stair, cost is just that stair's cost.

    // Create a dp table of size 'n'. dp[i] will store the minimum cost to reach stair 'i' (and pay its cost).
    vector<int> dp(n);
    // Initialize base cases for dp table.
    dp[0] = stairs[0];
    dp[1] = stairs[1];

    // Iterate from stair 2 up to the last stair (n-1).
    for(int i = 2; i < n; i++) {
        // The cost to reach stair 'i' is its own cost plus the minimum cost to reach either (i-1) or (i-2).
        int prevCost = min(dp[i-1], dp[i-2]);
        dp[i] = stairs[i] + prevCost;
    }

    // The final answer is the minimum cost to reach the 'top' (after the last stair).
    // This means comparing the cost to reach (n-1)th stair and then step,
    // or the cost to reach (n-2)th stair and then step.
    return min(dp[n-1], dp[n-2]);
}

// 4. Dynamic Programming - Space Optimization Approach
// Optimizes the bottom-up approach to use only constant space.
// Time Complexity: O(N) - Single loop.
// Space Complexity: O(1) - Uses only a few variables.
// 'stairs': Vector containing costs.
int minCostSpaceOpt(vector<int> &stairs) { // Renamed for clarity
    int n = stairs.size();

    // Handle edge cases for small 'n'.
    if (n == 0) return 0;
    if (n == 1) return stairs[0];

    // 'prev0' stores the minimum cost to reach stair (i-2).
    // 'prev1' stores the minimum cost to reach stair (i-1).
    // Initialize for i=2: prev0 for stair 0, prev1 for stair 1.
    int prev0 = stairs[0]; // Corresponds to dp[0]
    int prev1 = stairs[1]; // Corresponds to dp[1]

    // Iterate from stair 2 up to the last stair (n-1).
    for(int i = 2; i < n; i++) {
        // 'curr' calculates the minimum cost to reach current stair 'i'.
        int curr = stairs[i] + min(prev0, prev1);

        // Update for the next iteration:
        // 'prev0' becomes the old 'prev1' (now cost for (i-1)).
        // 'prev1' becomes the current 'curr' (now cost for 'i').
        prev0 = prev1;
        prev1 = curr;
    }

    // The final answer is the minimum of the cost to reach the last two stairs.
    // This is because you can reach the "top" from either stair (n-1) or stair (n-2).
    return min(prev0, prev1); // 'prev0' holds cost for (n-2), 'prev1' holds cost for (n-1) after loop.
}

// Main function for input/output and testing different approaches.
int main() {
    int n;
    cout << "Enter the count of stairs : ";
    cin >> n;

    vector<int> stairs(n);
    cout << "Enter the cost of stairs (space separated): ";
    for(int i = 0; i < n; i++) {
        cin >> stairs[i];
    }

    cout << "Costs: ";
    for(int cost : stairs) {
        cout << cost << " ";
    }
    cout << endl;

    // --- Uncomment one of the following lines to test different approaches ---

    // 1. Recursive (Brute Force) - Caution: Very slow for large N
    // int ans = min(minCostRec(stairs, n - 1), minCostRec(stairs, n - 2));

    // 2. DP - Top-Down (Memoization)
    vector<int> dp_memo(n, 0); // Initialize dp table with 0s
    // Need to handle small 'n' for memoization call if n<2
    if (n == 0) ans = 0;
    else if (n == 1) ans = stairs[0];
    else ans = min(minCostMemo(stairs, n - 1, dp_memo), minCostMemo(stairs, n - 2, dp_memo));

    // 3. DP - Bottom-Up (Tabulation)
    // int ans = minCostTab(stairs);

    // 4. DP - Space Optimization
    // int ans = minCostSpaceOpt(stairs);


    cout << "Minimum cost to reach the top: " << ans << endl;

    return 0; // Indicate successful execution.
}

1. Problem Statement

• Goal: Find the minimum cost to reach the top of a staircase.
• Input: An integer array cost where cost[i] is the cost of i-th step.
• Constraint: You can either climb one or two steps at a time.
• Starting Point: You can start from either step 0 or step 1.
• Reaching the Top: The “top” is considered one step beyond the last stair (index n). So, if there are n stairs, you need to reach index n.

2. Problem Insight

This problem is a classic Dynamic Programming problem with overlapping subproblems and optimal substructure. The key observation is that to reach a certain stair i, you must have come from either stair i-1 or stair i-2. The cost to reach i would then be cost[i] plus the minimum cost to reach i-1 or i-2.

Crucial Point: The goal is to reach the top, which is after the last actual stair. If there are n stairs (indexed 0 to n-1), the “top” can be thought of as position n. You can reach position n either from stair n-1 (taking 1 step) or from stair n-2 (taking 2 steps). Thus, the final answer will be the minimum of dp[n-1] and dp[n-2].

3. Approaches to Solving

A. Recursive Approach (Brute Force)

• Idea: Directly translate the recurrence relation. minCost(i) represents the minimum cost to reach stair i.
• Recurrence: minCost(i) = cost[i] + min(minCost(i-1), minCost(i-2))
• Base Cases:
  • minCost(-1) (or i < 0): 0 (cost to reach an imaginary step before the stairs, typically 0 for initialization)
  • minCost(0): cost[0]
  • minCost(1): cost[1]
• Function Call in main: min(minCost(stairs, n-1), minCost(stairs, n-2)) because you can start from 0 or 1, and the last two steps can lead to the ‘top’.
• Pros: Simple to write.
• Cons: Highly inefficient due to redundant calculations (overlapping subproblems).
• Time Complexity: $O(2^N)$ (Exponential, as it forms a recursion tree).
• Space Complexity: $O(N)$ (Due to recursion stack depth).

B. Dynamic Programming - Top-Down (Memoization)

• Idea: Optimize the recursive approach by storing the results of already computed subproblems in a dp table. Before computing minCost(i), check if it’s already in the dp table. If yes, return the stored value; otherwise, compute and store it.
• Pros: Overcomes redundant calculations of pure recursion.
• Cons: Still uses a recursion stack.
• Time Complexity: $O(N)$ (Each minCost(i) is computed only once).
• Space Complexity: $O(N)$ (For dp array) + $O(N)$ (For recursion stack) = $O(N)$.

C. Dynamic Programming - Bottom-Up (Tabulation)

• Idea: Build the solution iteratively from the base cases upwards.
• Steps:
  1. Initialize dp[0] = cost[0] and dp[1] = cost[1].
  2. Iterate from i = 2 to n-1 (for stairs 2 up to n-1).
  3. For each i, dp[i] = cost[i] + min(dp[i-1], dp[i-2]). dp[i] now stores the minimum cost to reach stair i and pay its cost.
  4. The final answer is min(dp[n-1], dp[n-2]). This is because to reach the “top” (after n-1 stair), you can either step from n-1 (cost dp[n-1]) or from n-2 (cost dp[n-2]).
• Pros: No recursion stack overhead. Often preferred for its iterative nature and clear flow.
• Cons: Requires an array of size $N$.
• Time Complexity: $O(N)$ (Single loop).
• Space Complexity: $O(N)$ (For dp array).

D. Dynamic Programming - Space Optimization

• Idea: Observe that to calculate the current minimum cost to reach stair i, we only need the minimum costs to reach stairs i-1 and i-2. We don’t need the entire dp array. We can use just two variables (prev0, prev1) to store these previous two costs.
• Steps:
  1. Initialize prev0 = cost[0] and prev1 = cost[1].
  2. Iterate from i = 2 to n-1.
  3. Calculate curr = cost[i] + min(prev0, prev1).
  4. Update for next iteration: prev0 = prev1; prev1 = curr;
  5. The final answer is min(prev0, prev1).
• Pros: Extremely efficient in terms of space.
• Cons: Only applicable when current state depends only on a few previous states.
• Time Complexity: $O(N)$ (Single loop).
• Space Complexity: $O(1)$ (Constant space, regardless of N).

4. Important Considerations

• Meaning of dp[i]: In this problem, dp[i] usually represents the minimum cost to reach stair i (including the cost of stair i).
• Reaching the Top: The “top” is an imaginary step after the last stair. If there are n stairs (0 to n-1), the top is essentially index n. You can reach n from n-1 or n-2. So, the minimum cost to reach the top is min(dp[n-1], dp[n-2]).
• Edge Cases for n: Pay attention to small n values (e.g., n=0, n=1, n=2) as they are often base cases or require special handling. Your code correctly handles n=0 by returning 0, and n=1 and n=2 directly in recursive/memoized solutions. In tabulation/space optimization, n=0 or n=1 might be handled implicitly or require an if block at the start. For n=0 or n=1 stairs, the loop for i=2 to n-1 won’t run, and prev0, prev1 (or dp[0], dp[1]) will contain the costs.

---