Prefix and Suffix Search

Description

You are given an integer array cost where cost[i] represents the cost of stepping on the i-th stair. Once you pay the cost at a particular step, you can choose to climb either one step or two steps forward.

You may begin your climb from either step 0 or step 1 (both are free to start from — you only pay when you leave a step).

Return the minimum total cost to reach the top of the staircase. The "top" is one position beyond the last element of the array (i.e., position n where n is the length of cost).

Examples

Example 1

Input: cost = [10, 15, 20]

Output: 15

Explanation: We start at step 1 (cost 15). From step 1, we climb two steps to reach the top. The total cost is 15. Starting from step 0 and climbing optimally would cost at least 10 + 20 = 30 (step 0 → step 2 → top), or 10 + 15 = 25 (step 0 → step 1 → top minus the cheaper continuation). The cheapest overall path is simply starting at step 1 and jumping straight to the top for a cost of 15.

Example 2

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

Output: 6

Explanation: Starting at step 0:

Pay 1, climb two steps to step 2.
Pay 1, climb two steps to step 4.
Pay 1, climb two steps to step 6.
Pay 1, climb one step to step 7.
Pay 1, climb two steps to step 9.
Pay 1, climb one step to the top.
Total cost = 6. The key strategy is to skip over the expensive steps (cost 100) whenever possible by taking two-step jumps.

Constraints

2 ≤ cost.length ≤ 1000
0 ≤ cost[i] ≤ 999

Editorial

Brute Force

Intuition

The most natural way to think about this problem is: at every step, you have two choices — climb one step or climb two steps. So we can try every possible combination of one-step and two-step climbs, calculate the total cost for each path, and pick the cheapest one.

Imagine you are standing at the bottom of a staircase with price tags on each step. You want to reach the top spending as little money as possible. The brute force idea is like a traveler trying every route on a map — exhaustive but guaranteed to find the cheapest path.

We can model this with recursion. Define minCost(i) as the minimum cost to reach step i. To reach step i, you must have come from either step i-1 (paying cost[i-1]) or step i-2 (paying cost[i-2]). The base cases are minCost(0) = 0 and minCost(1) = 0 because you can start from either step for free.

Step-by-Step Explanation

Let's trace through with cost = [10, 15, 20]. We want minCost(3) (reaching the top, which is one position past the last step).

Step 1: Call minCost(3). To reach step 3, we can come from step 2 (paying cost[2]=20) or step 1 (paying cost[1]=15). We need minCost(2) and minCost(1).

Step 2: Recurse into minCost(2). To reach step 2, we can come from step 1 (paying cost[1]=15) or step 0 (paying cost[0]=10). We need minCost(1) and minCost(0).

Step 3: Recurse into minCost(1). This is a base case — we can start at step 1 for free. Return 0.

Step 4: Recurse into minCost(0). This is also a base case — we can start at step 0 for free. Return 0.

Step 5: Now we can compute minCost(2) = min(minCost(1) + cost[1], minCost(0) + cost[0]) = min(0 + 15, 0 + 10) = 10.

Step 6: Back to minCost(3): we still need minCost(1). Recurse into minCost(1) again — this is the SAME call we already made! We recompute it: return 0.

Step 7: Now compute minCost(3) = min(minCost(2) + cost[2], minCost(1) + cost[1]) = min(10 + 20, 0 + 15) = min(30, 15) = 15.

Result: The minimum cost is 15.

Notice that minCost(1) was called TWICE — once from minCost(2) and once from minCost(3). This redundant computation is the hallmark of overlapping subproblems and is what makes this approach exponential.

Brute Force Recursion — Overlapping Subproblems — Watch how the recursive calls branch out and the same subproblems (like minCost(1)) get recomputed multiple times, revealing overlapping subproblems.

Algorithm

Define a recursive function minCost(i) that returns the minimum cost to reach step i.
Base cases: minCost(0) = 0 and minCost(1) = 0 (you can start from either step for free).
Recursive case: minCost(i) = min(minCost(i-1) + cost[i-1], minCost(i-2) + cost[i-2]).
Call minCost(n) where n = len(cost) to get the minimum cost to reach the top.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        return minCost(cost, n);
    }

private:
    int minCost(vector<int>& cost, int i) {
        if (i <= 1) return 0;
        return min(minCost(cost, i - 1) + cost[i - 1],
                   minCost(cost, i - 2) + cost[i - 2]);
    }
};

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)

        def min_cost(i: int) -> int:
            if i <= 1:
                return 0
            return min(min_cost(i - 1) + cost[i - 1],
                       min_cost(i - 2) + cost[i - 2])

        return min_cost(n)

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        return minCost(cost, n);
    }

    private int minCost(int[] cost, int i) {
        if (i <= 1) return 0;
        return Math.min(minCost(cost, i - 1) + cost[i - 1],
                        minCost(cost, i - 2) + cost[i - 2]);
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each step, we make two recursive calls (for i-1 and i-2), and many subproblems are recomputed. The recursion tree has an exponential number of nodes. For the Fibonacci-like recurrence, the number of calls grows as O(2^n).

Space Complexity: O(n)

The recursion stack can go as deep as n levels (each call reduces i by at least 1), so the call stack uses O(n) space.

Why This Approach Is Not Efficient

The brute force recursion has O(2^n) time complexity because it recomputes the same subproblems over and over. In our trace, minCost(1) was computed twice. For larger inputs, this gets dramatically worse:

For n = 10: roughly 1,024 calls
For n = 20: roughly 1,048,576 calls
For n = 1000 (the constraint limit): astronomically many — completely infeasible

The root cause is overlapping subproblems: minCost(i) depends on minCost(i-1) and minCost(i-2), and minCost(i-1) also depends on minCost(i-2). So minCost(i-2) gets computed by both paths.

The fix is simple: remember (memoize) the result of each subproblem the first time we compute it, so we never recompute it. This is the essence of dynamic programming.

Better Approach - Memoization (Top-Down DP)

Intuition

The brute force recursion is correct — it just does too much repeated work. The insight of memoization is: keep a "notebook" (memo table) where you write down the answer to each subproblem the first time you solve it. Before computing any subproblem, check your notebook first. If the answer is already there, use it immediately instead of recomputing.

This is like a student solving practice problems. The first time they encounter "What is 7 × 8?", they work it out. But if they write "7 × 8 = 56" in their notes, the next time they see it, they just look it up instantly.

With memoization, each of the n+1 subproblems (minCost(0) through minCost(n)) is computed exactly once. The total work drops from O(2^n) to O(n).

Step-by-Step Explanation

Let's trace with cost = [10, 15, 20] and a memo table initialized to [0, 0, ?, ?] (base cases pre-filled).

Step 1: Initialize memo table: memo = [0, 0, null, null]. Base cases memo[0]=0 and memo[1]=0 are known.

Step 2: Call minCost(3). memo[3] is null, so we need to compute it. First, we need minCost(2).

Step 3: Call minCost(2). memo[2] is null, so we need to compute it. We need minCost(1) and minCost(0).

Step 4: Look up minCost(1) in memo → memo[1] = 0. Found instantly, no recursion needed!

Step 5: Look up minCost(0) in memo → memo[0] = 0. Found instantly again!

Step 6: Compute memo[2] = min(memo[1] + cost[1], memo[0] + cost[0]) = min(0+15, 0+10) = 10. Store in memo.

Step 7: Back to minCost(3). We need minCost(1) — look it up in memo → 0. Cache hit! No recomputation.

Step 8: Compute memo[3] = min(memo[2] + cost[2], memo[1] + cost[1]) = min(10+20, 0+15) = 15. Store in memo.

Step 9: Return memo[3] = 15.

The memo table saved us from recomputing minCost(1). With larger inputs, the savings are dramatic.

Memoization — Top-Down DP Table Filling — Watch how the memo table gets populated as recursive calls resolve. Notice how base cases are used immediately and no subproblem is computed twice.

Algorithm

Create a memo array of size n+1, initialized with sentinel values (e.g., -1).
Set base cases: memo[0] = 0, memo[1] = 0.
Define recursive function minCost(i):
- If memo[i] is already computed, return it immediately.
- Otherwise, compute memo[i] = min(minCost(i-1) + cost[i-1], minCost(i-2) + cost[i-2]).
- Store the result in memo[i] and return it.
Call minCost(n) to get the answer.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> memo(n + 1, -1);
        return minCost(cost, n, memo);
    }

private:
    int minCost(vector<int>& cost, int i, vector<int>& memo) {
        if (i <= 1) return 0;
        if (memo[i] != -1) return memo[i];
        memo[i] = min(minCost(cost, i - 1, memo) + cost[i - 1],
                      minCost(cost, i - 2, memo) + cost[i - 2]);
        return memo[i];
    }
};

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
        memo = {}

        def min_cost(i: int) -> int:
            if i <= 1:
                return 0
            if i in memo:
                return memo[i]
            memo[i] = min(min_cost(i - 1) + cost[i - 1],
                          min_cost(i - 2) + cost[i - 2])
            return memo[i]

        return min_cost(n)

import java.util.Arrays;

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return minCost(cost, n, memo);
    }

    private int minCost(int[] cost, int i, int[] memo) {
        if (i <= 1) return 0;
        if (memo[i] != -1) return memo[i];
        memo[i] = Math.min(minCost(cost, i - 1, memo) + cost[i - 1],
                           minCost(cost, i - 2, memo) + cost[i - 2]);
        return memo[i];
    }
}

Complexity Analysis

Time Complexity: O(n)

Each subproblem minCost(i) for i from 0 to n is computed at most once and cached. There are n+1 subproblems, and each takes O(1) work (two lookups and a min operation). Total: O(n).

Space Complexity: O(n)

The memo array stores n+1 values, requiring O(n) space. Additionally, the recursion stack can be up to O(n) deep. Total space: O(n).

Why This Approach Is Not Efficient

Memoization reduces the time complexity from O(2^n) to O(n) — a massive improvement. However, it still uses O(n) extra space for two reasons:

Memo array: Stores all n+1 subproblem results.
Recursion stack: The recursive calls can go up to n levels deep.

For n = 1000 (the constraint limit), this means allocating an array of 1001 integers and a call stack 1000 frames deep. While this is acceptable, we can do better.

The key observation is: to compute dp[i], we only need dp[i-1] and dp[i-2]. We don't need to remember dp[0] through dp[i-3] anymore. This means we can replace the entire memo array with just two variables, reducing space from O(n) to O(1). We can also eliminate the recursion overhead by computing bottom-up.

Optimal Approach - Bottom-Up DP with Constant Space

Intuition

Instead of computing from the top down (starting at minCost(n) and recursing backward), we flip the direction and compute from the bottom up. Start from the base cases and work forward, building up the answer step by step.

The crucial insight is that at any point during this bottom-up computation, we only ever look back at the previous two values. Think of it like climbing the staircase in real life: to decide the cheapest way to reach your current step, you only need to know the cheapest way to reach the step right below you and the step two below you. You don't care how you got to those earlier steps.

So instead of keeping an entire array of past results, we maintain just two variables: prev2 (cost to reach two steps back) and prev1 (cost to reach one step back). As we advance, these variables slide forward like a window of size 2, giving us O(1) space.

Step-by-Step Explanation

Let's trace with cost = [10, 15, 20].

Step 1: Initialize: prev2 = 0 (cost to reach step 0), prev1 = 0 (cost to reach step 1). Both are free starting positions.

Step 2: i = 2. To reach step 2, compare two paths:

From step 1: prev1 + cost[1] = 0 + 15 = 15
From step 0: prev2 + cost[0] = 0 + 10 = 10

Step 3: current = min(15, 10) = 10. The cheaper path to step 2 is through step 0.

Step 4: Slide the window forward: prev2 ← prev1 = 0, prev1 ← current = 10.

Step 5: i = 3 (the top). To reach step 3, compare two paths:

From step 2: prev1 + cost[2] = 10 + 20 = 30
From step 1: prev2 + cost[1] = 0 + 15 = 15

Step 6: current = min(30, 15) = 15. The cheaper path to the top is starting from step 1 directly (cost 15).

Step 7: Slide the window forward: prev2 ← prev1 = 10, prev1 ← current = 15.

Step 8: Loop ends. Return prev1 = 15.

We used only two variables throughout — no array, no recursion stack. The same answer as before, but with O(1) space.

Bottom-Up DP — Sliding Two Variables Over the Cost Array — Watch how two variables (prev2 and prev1) slide forward along the cost array, computing the minimum cost at each step using only the previous two results.

Algorithm

Initialize two variables: prev2 = 0 (cost to reach step 0) and prev1 = 0 (cost to reach step 1).
Loop from i = 2 to n (inclusive):
- Compute current = min(prev1 + cost[i-1], prev2 + cost[i-2]).
- Slide the window: prev2 = prev1, prev1 = current.
Return prev1, which now holds the minimum cost to reach step n (the top).

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        int prev2 = 0, prev1 = 0;

        for (int i = 2; i <= n; i++) {
            int current = min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
};

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
        prev2, prev1 = 0, 0

        for i in range(2, n + 1):
            current = min(prev1 + cost[i - 1], prev2 + cost[i - 2])
            prev2 = prev1
            prev1 = current

        return prev1

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev2 = 0, prev1 = 0;

        for (int i = 2; i <= n; i++) {
            int current = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the cost array once with a single loop from 2 to n. Each iteration performs a constant amount of work (one min operation, two additions, and two variable assignments). Total: O(n).

Space Complexity: O(1)

We use only three variables (prev2, prev1, current) regardless of input size. No arrays, no recursion stack. This is the optimal space usage for this problem — we need at least the two previous values to compute the next one, and we achieve exactly that.