Problem Statement

Given an integer array fee where fee[i] represents the cost to step onto the ith stair. After paying this fee, you may advance either one or two steps upward.

You can begin climbing from either stair 0 or stair 1 without incurring any initial expense.

Calcluate and return the minimum cost required to reach beyond the final stair (the "summit").

Example 1:

Input: fee = [10, 15, 20]
Output: 15
Explanation: Start at index 1. Pay 15 and climb two steps to reach the summit.

Example 2:

Input: fee = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Start at index 0 and make optimal jumps to minimize total expense.

Core DP Strategy

This problem exhibits optimal substructure similar to Fibonacci sequence modeling. We present two complementary dynamic programming perspectives.

Forward-Progressign Method

1. State Representation

Define minExpense[pos] as the minimum total cost required to stand exactly on stair pos.

2. Recurrence Relation

To reach stair pos, consider two exclusive paths:

• Arrive from pos-1: incur minExpense[pos-1] plus fee[pos-1] for the final single-step jump
• Arrive from pos-2: incur minExpense[pos-2] plus fee[pos-2] for the final double-step jump

The optimal choice is:

minExpense[pos] = min(minExpense[pos-1] + fee[pos-1], minExpense[pos-2] + fee[pos-2])

3. Boundary Conditions

Since stairs 0 and 1 are free starting points:

minExpense[0] = 0
minExpense[1] = 0

4. Tabulation Order

Compute values sequentially from index 2 through n (where n equals array length), ensuring all dependencies are resolved before they're needed.

5. Solution Extraction

The summit resides at position n, making minExpense[n] the final answer.

Backward-Looking Method

1. State Representation

Define remainingCost[pos] as the minimum expense required to travel from stair pos to the summit.

2. Recurrence Relation

When positioned at stair pos:

• Pay fee[pos] and jump to pos+1, then follow optimal path remainingCost[pos+1]
• Pay fee[pos] and jump to pos+2, then follow optimal path remainingCost[pos+2]

Thus:

remainingCost[pos] = fee[pos] + min(remainingCost[pos+1], remainingCost[pos+2])

3. Boundary Conditions

The final two stairs lead directly to the summit:

remainingCost[n-1] = fee[n-1]
remainingCost[n-2] = fee[n-2]

4. Tabulation Order

Process indices in descending order from n-3 down to 0, as each state relies on future states.

5. Solution Extraction

The optimal starting point is the cheaper of the first two stairs: min(remainingCost[0], remainingCost[1]).

Reference Implementation

Forward DP Solution

int calculateMinCost(int* fee, int n) {
    int* minExpense = new int[n + 1];
    minExpense[0] = 0;
    minExpense[1] = 0;
    
    for (int pos = 2; pos <= n; ++pos) {
        int fromPrevious = minExpense[pos - 1] + fee[pos - 1];
        int fromEarlier = minExpense[pos - 2] + fee[pos - 2];
        minExpense[pos] = (fromPrevious < fromEarlier) ? fromPrevious : fromEarlier;
    }
    
    int result = minExpense[n];
    delete[] minExpense;
    return result;
}

Complexity Analysis:

• Time: O(n) single pass through the array
• Space: O(n) for the DP table

Backward DP Solution

int calculateMinCostReverse(int* fee, int n) {
    int* remainingCost = new int[n];
    remainingCost[n - 1] = fee[n - 1];
    remainingCost[n - 2] = fee[n - 2];
    
    for (int pos = n - 3; pos >= 0; --pos) {
        int singleJump = remainingCost[pos + 1];
        int doubleJump = remainingCost[pos + 2];
        remainingCost[pos] = fee[pos] + ((singleJump < doubleJump) ? singleJump : doubleJump);
    }
    
    int result = (remainingCost[0] < remainingCost[1]) ? remainingCost[0] : remainingCost[1];
    delete[] remainingCost;
    return result;
}

Complexity Analysis:

• Time: O(n) single reverse pass through the array
• Space: O(n) for the DP table