DSA-127 · FOCUSED PRACTICE

Min Cost Climbing Stairs

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 9863 deterministic checks. Learner drafts are not executed.

Understand the problem

cost[i] is the nonnegative cost paid when leaving stair i. You may start on stair 0 or stair 1 without an initial payment and then move up one or two stairs at a time. The top is position cost.length, beyond the final charged stair. Return the minimum total cost to reach the top.

cost must be non-null, contain at most 100,000 entries, and contain only nonnegative int values, including Integer.MAX_VALUE. Null throws NullPointerException; a negative entry or oversized array throws IllegalArgumentException. Validate the complete array before any short-array return.
The top is position n, not n−1. Starting at 0 or 1 is free, but departing a charged stair pays its cost. For n=0 or n=1 return 0: the top is already an allowed starting position. Empty and single-entry inputs are deliberately supported extensions.
Return an exact long minimum, preserve every input entry, and return only the value, not a chosen route. Nonnegative costs allow an optimal route that ends exactly at the top; overshooting never improves on the direct available final landing. The recursive baseline is for bounded small inputs only.

Examples

Input: cost=[10,15,20]
Output: 15
Start at 1 and pay 15 to jump to top 3. Paying 10 then 20 costs 30.
Input: cost=[1,100,1,1,1,100,1,1,100,1]
Output: 6
One optimal charged sequence visits indices 0,2,4,6,7,9 before the top. The cheapest first stair alone does not determine the whole route.
Input: cost=[9]
Output: 0
Start directly at top position 1; index 0 need not be visited.
Input: cost=[2147483647,2147483647,2147483647,2147483647]
Output: 4294967294
Any route must depart at least two charged stairs. Their total exceeds int but fits long.

Before you start

A destination-state definition distinct from cost paid on a stair
Two-predecessor rolling state and long arithmetic

Recognize the structure

At destination t, the immediately preceding charged stair must be t−1 or t−2. Payment belongs to that predecessor, and the cheapest way to arrive there is a repeated subproblem. The state represents cost to reach a position before paying to depart it. This phrasing determines the bases, indexing, and recurrence; mixing it with a paid-on-landing state is the most common source of an off-by-one error.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 125/20,000 characters

Self-review

I can state whether the cost is paid before arrival or on departure and identify the top index.I can derive both bases and attach each cost index to the correct predecessor.I can explain why the small-input baseline is equivalent under nonnegative costs and why long addition is exact.

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

Which two stairs can immediately precede a destination t?

Hint 2

Let the state mean minimum cost to arrive, before paying to leave. What are the costs of both free starts?

Hint 3

Use min(D(t−1)+cost[t−1], D(t−2)+cost[t−2]); preserve both old registers until next is computed.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate all one-step and two-step continuations

From a chosen starting stair i, pay cost[i] and recursively minimize continuing at i+1 or i+2. At or beyond the top return zero. Take the minimum of starting at 0 and 1. Under the nonnegative contract an overshooting terminal branch cannot beat a path that jumps directly to the top from the same last stair; both jumps have the same departure cost. This suffix enumeration is a different state from the prefix reference, but computes the same objective. Repeated suffixes cause O(2^n) upper-bound time and O(n+1) call-stack depth. Tests compare the baseline only on small arrays; large-array validation and the reference use no recursive calls.

Improve the baseline

Define arrival cost precisely

Let D(t) be the least total cost paid to arrive at position t before paying anything to leave it. Set D(0)=D(1)=0 because both are free starts. If n=0, only D(0) is relevant. A two-register implementation may initialize both virtual base registers anyway; no cost entry is read until t=2.

Charge the predecessor, not the destination

For t≥2, D(t)=min(D(t−1)+cost[t−1], D(t−2)+cost[t−2]). The last jump is length one or two. There is no cost[t] term: when t=n the index would be outside the array, and the top has no departure charge. For [10,15,20], D(2)=10 and D(3)=min(10+20,0+15)=15.

Use increasing destinations

Each candidate reads a smaller finalized destination cost. A conceptual D table for [1,100,1,1] is [0,0,1,2,2]. Keeping this table initially makes the contract visible. The dependency graph has no cycles because both moves strictly increase the stair position.

Compress the live boundary

Before destination t, previousTwo=D(t−2) and previousOne=D(t−1). Compute fromTwo and fromOne in long arithmetic, choose next, then shift the pair. The two candidate values are shown separately in the trace so the source of each cost is visible. Saving the complete table is unnecessary when only the final number is returned.

Separate validation, arithmetic, and route output

Scan all entries for negative values before computing. Since a route pays at most n nonnegative int charges, n×Integer.MAX_VALUE is an easy safe upper bound below long capacity for n≤100000. A long register on the left of addition promotes the int cost before addition. The reference returns no route; reconstruction needs extra predecessor decisions or a second carefully specified computation.

Why it is correct

Free-start bases

No charge has been paid at starting positions 0 and 1, so zero is attainable. Nonnegative costs rule out a cheaper negative route. For n≤1, an allowed start is already the top, proving the zero answer.

Exhaustive final-jump cases

Any exact route to t≥2 has a last jump from t−1 or t−2 and pays that predecessor cost. If its prefix cost were larger than the optimal arrival cost at that predecessor, replacing the prefix would improve the route. Conversely either candidate appends a valid jump to an optimal prefix. Their minimum is exactly D(t).

Induction, compression, and termination

The initialized pair supplies the two bases. Assuming the invariant before t, the two long candidates calculate D(t); shifting establishes the next invariant without reading the overwritten predecessor. The loop visits destinations 2 through n and returns D(n). The validation and finite loop terminate, the input remains read-only, and all additions stay within the stated bound.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Objects;

public final class Solution {
    private Solution() {}
    private static void validate(int[] cost) {
        Objects.requireNonNull(cost, "cost");
        if (cost.length > 100_000) throw new IllegalArgumentException("too many steps");
        for (int value : cost) if (value < 0) throw new IllegalArgumentException("negative cost");
    }
    public static long minCostClimbingStairs(int[] cost) {
        validate(cost);
        long previousTwo = 0, previousOne = 0;
        for (int top = 2; top <= cost.length; top++) {
            long fromTwo = previousTwo + cost[top - 2];
            long fromOne = previousOne + cost[top - 1];
            long next = Math.min(fromTwo, fromOne);
            previousTwo = previousOne;
            previousOne = next;
        }
        return previousOne;
    }
    // Baseline: enumerate every continuation; only small arrays are practical.
    public static long baseline(int[] cost) {
        validate(cost);
        return Math.min(walk(cost, 0), walk(cost, 1));
    }
    private static long walk(int[] cost, int step) {
        if (step >= cost.length) return 0;
        return (long) cost[step] + Math.min(walk(cost, step + 1), walk(cost, step + 2));
    }
}

Read the meaningful blocks

Validate the whole source

Objects.requireNonNull gives the explicit null outcome. Length and value checks happen even on [−1], whose length alone might tempt an early zero return. Validation is part of the API and contributes linear time.

Name both incoming costs

fromTwo adds cost[top−2] to the two-back arrival; fromOne adds cost[top−1] to the one-back arrival. These names make a mismatch of cost index and predecessor visible during review.

Commit after comparison

Math.min chooses the complete new destination cost. Only then shift previousTwo and previousOne. For n≤1 the loop is empty and the initialized previousOne is the documented zero; no array element is read.

Complexity

For n entries, validation plus n−1 or fewer transitions costs O(n+1) time. The reference uses O(1) auxiliary storage and returns one long; input storage and the displayed teaching history are excluded.

The suffix-enumeration baseline uses O(2^n) upper-bound time and O(n+1) recursion stack. A memoized suffix alternative uses O(n) cache and stack; a full prefix table uses O(n) space and readily supports path reconstruction. The constant-space reference is appropriate when only the minimum value is required.

Exact-state walkthroughs

Reveal normal and boundary traces

Two predecessor prices compete

Input: [10,15,20] · Minimum departure cost to top: 15

Step 1 of 8: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

Minimum stair cost — pay at the predecessor

Phase: validated.

D(t) = min(D(t−2) + cost[t−2], D(t−1) + cost[t−1])

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Charged stairs — top is position n, beyond the last entry.

0: 10available in this pass
1: 15available in this pass
2: 20available in this pass

Top position 3 has no charge. Starting on position 0 or 1 costs zero before departure. D(t) is an arrival cost.

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
Variable	Value
input	`[10,15,20]`
phase	`"validated"`
caseResults	`[]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] cost) {
 6         Objects.requireNonNull(cost, "cost");
 7         if (cost.length > 100_000) throw new IllegalArgumentException("too many steps");
 8         for (int value : cost) if (value < 0) throw new IllegalArgumentException("negative cost");
 9     }
10     public static long minCostClimbingStairs(int[] cost) {
11         validate(cost);
12         long previousTwo = 0, previousOne = 0;
13         for (int top = 2; top <= cost.length; top++) {
14             long fromTwo = previousTwo + cost[top - 2];
15             long fromOne = previousOne + cost[top - 1];
16             long next = Math.min(fromTwo, fromOne);
17             previousTwo = previousOne;
18             previousOne = next;
19         }
20         return previousOne;
21     }
22     // Baseline: enumerate every continuation; only small arrays are practical.
23     public static long baseline(int[] cost) {
24         validate(cost);
25         return Math.min(walk(cost, 0), walk(cost, 1));
26     }
27     private static long walk(int[] cost, int step) {
28         if (step >= cost.length) return 0;
29         return (long) cost[step] + Math.min(walk(cost, step + 1), walk(cost, step + 2));
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
input
[10,15,20]
phase
"validated"
caseResults
[]
Both allowed starting destinations have zero arrival cost.
D(t) is cost to arrive before paying to depart. Top is n, beyond every charged stair. The two initial registers are zero even when no loop iteration is required.
input
[10,15,20]
phase
"range-start"
caseResults
[]
table
[0,0,null,null]
previousTwo
0
previousOne
0
position
1
Compare both complete incoming routes, including predecessor charges.
fromTwo=D(t−2)+cost[t−2]; fromOne=D(t−1)+cost[t−1]. Both registers are still old. No cost is charged at destination t itself.
input
[10,15,20]
phase
"candidate"
caseResults
[]
table
[0,0,null,null]
previousTwo
0
previousOne
0
position
2
two
10
one
15
next
10
Store the minimum arrival cost and move the frontier.
The new pair is D(t−1), D(t). The reference retains no full table and never writes a cost entry. A tie needs no path preference for a value-only result.
input
[10,15,20]
phase
"commit"
caseResults
[]
table
[0,0,10,null]
previousTwo
0
previousOne
10
position
2
two
10
one
15
next
10
Compare both complete incoming routes, including predecessor charges.
fromTwo=D(t−2)+cost[t−2]; fromOne=D(t−1)+cost[t−1]. Both registers are still old. No cost is charged at destination t itself.
input
[10,15,20]
phase
"candidate"
caseResults
[]
table
[0,0,10,null]
previousTwo
0
previousOne
10
position
3
two
15
one
30
next
15
Store the minimum arrival cost and move the frontier.
The new pair is D(t−1), D(t). The reference retains no full table and never writes a cost entry. A tie needs no path preference for a value-only result.
input
[10,15,20]
phase
"commit"
caseResults
[]
table
[0,0,10,15]
previousTwo
10
previousOne
15
position
3
two
15
one
30
next
15
Return the arrival cost at the top position.
For n=0 or 1 a free start is already the top, so the empty loop returns zero. All shown long fixture values are exactly representable in JavaScript; upper-bound Java tests are separate.
input
[10,15,20]
phase
"range-complete"
caseResults
[]
table
[0,0,10,15]
previousTwo
10
previousOne
15
position
3
answer
15
Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
result
15

No charged stairs

Input: [] · Minimum departure cost to top: 0

Step 1 of 4: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

Minimum stair cost — pay at the predecessor

Phase: validated.

D(t) = min(D(t−2) + cost[t−2], D(t−1) + cost[t−1])

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Charged stairs — top is position n, beyond the last entry.

No entries.

Top position 0 has no charge. Starting on position 0 or 1 costs zero before departure. D(t) is an arrival cost.

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
Variable	Value
input	`[]`
phase	`"validated"`
caseResults	`[]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] cost) {
 6         Objects.requireNonNull(cost, "cost");
 7         if (cost.length > 100_000) throw new IllegalArgumentException("too many steps");
 8         for (int value : cost) if (value < 0) throw new IllegalArgumentException("negative cost");
 9     }
10     public static long minCostClimbingStairs(int[] cost) {
11         validate(cost);
12         long previousTwo = 0, previousOne = 0;
13         for (int top = 2; top <= cost.length; top++) {
14             long fromTwo = previousTwo + cost[top - 2];
15             long fromOne = previousOne + cost[top - 1];
16             long next = Math.min(fromTwo, fromOne);
17             previousTwo = previousOne;
18             previousOne = next;
19         }
20         return previousOne;
21     }
22     // Baseline: enumerate every continuation; only small arrays are practical.
23     public static long baseline(int[] cost) {
24         validate(cost);
25         return Math.min(walk(cost, 0), walk(cost, 1));
26     }
27     private static long walk(int[] cost, int step) {
28         if (step >= cost.length) return 0;
29         return (long) cost[step] + Math.min(walk(cost, step + 1), walk(cost, step + 2));
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
input
[]
phase
"validated"
caseResults
[]
Both allowed starting destinations have zero arrival cost.
D(t) is cost to arrive before paying to depart. Top is n, beyond every charged stair. The two initial registers are zero even when no loop iteration is required.
input
[]
phase
"range-start"
caseResults
[]
table
[0]
previousTwo
0
previousOne
0
position
0
Return the arrival cost at the top position.
For n=0 or 1 a free start is already the top, so the empty loop returns zero. All shown long fixture values are exactly representable in JavaScript; upper-bound Java tests are separate.
input
[]
phase
"range-complete"
caseResults
[]
table
[0]
previousTwo
0
previousOne
0
position
0
answer
0
Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
result
0

Free start is already the top

Input: [9] · Minimum departure cost to top: 0

Step 1 of 4: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

Minimum stair cost — pay at the predecessor

Phase: validated.

D(t) = min(D(t−2) + cost[t−2], D(t−1) + cost[t−1])

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Charged stairs — top is position n, beyond the last entry.

0: 9available in this pass

Top position 1 has no charge. Starting on position 0 or 1 costs zero before departure. D(t) is an arrival cost.

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
Variable	Value
input	`[9]`
phase	`"validated"`
caseResults	`[]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] cost) {
 6         Objects.requireNonNull(cost, "cost");
 7         if (cost.length > 100_000) throw new IllegalArgumentException("too many steps");
 8         for (int value : cost) if (value < 0) throw new IllegalArgumentException("negative cost");
 9     }
10     public static long minCostClimbingStairs(int[] cost) {
11         validate(cost);
12         long previousTwo = 0, previousOne = 0;
13         for (int top = 2; top <= cost.length; top++) {
14             long fromTwo = previousTwo + cost[top - 2];
15             long fromOne = previousOne + cost[top - 1];
16             long next = Math.min(fromTwo, fromOne);
17             previousTwo = previousOne;
18             previousOne = next;
19         }
20         return previousOne;
21     }
22     // Baseline: enumerate every continuation; only small arrays are practical.
23     public static long baseline(int[] cost) {
24         validate(cost);
25         return Math.min(walk(cost, 0), walk(cost, 1));
26     }
27     private static long walk(int[] cost, int step) {
28         if (step >= cost.length) return 0;
29         return (long) cost[step] + Math.min(walk(cost, step + 1), walk(cost, step + 2));
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
input
[9]
phase
"validated"
caseResults
[]
Both allowed starting destinations have zero arrival cost.
D(t) is cost to arrive before paying to depart. Top is n, beyond every charged stair. The two initial registers are zero even when no loop iteration is required.
input
[9]
phase
"range-start"
caseResults
[]
table
[0,0]
previousTwo
0
previousOne
0
position
1
Return the arrival cost at the top position.
For n=0 or 1 a free start is already the top, so the empty loop returns zero. All shown long fixture values are exactly representable in JavaScript; upper-bound Java tests are separate.
input
[9]
phase
"range-complete"
caseResults
[]
table
[0,0]
previousTwo
0
previousOne
0
position
1
answer
0
Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
result
0

Long result beyond int

Input: [2147483647,2147483647,2147483647,2147483647] · Minimum departure cost to top: 4294967294

Step 1 of 10: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

Minimum stair cost — pay at the predecessor

Phase: validated.

D(t) = min(D(t−2) + cost[t−2], D(t−1) + cost[t−1])

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Charged stairs — top is position n, beyond the last entry.

0: 2147483647available in this pass
1: 2147483647available in this pass
2: 2147483647available in this pass
3: 2147483647available in this pass

Top position 4 has no charge. Starting on position 0 or 1 costs zero before departure. D(t) is an arrival cost.

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
Variable	Value
input	`[2147483647,2147483647,2147483647,2147483647]`
phase	`"validated"`
caseResults	`[]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] cost) {
 6         Objects.requireNonNull(cost, "cost");
 7         if (cost.length > 100_000) throw new IllegalArgumentException("too many steps");
 8         for (int value : cost) if (value < 0) throw new IllegalArgumentException("negative cost");
 9     }
10     public static long minCostClimbingStairs(int[] cost) {
11         validate(cost);
12         long previousTwo = 0, previousOne = 0;
13         for (int top = 2; top <= cost.length; top++) {
14             long fromTwo = previousTwo + cost[top - 2];
15             long fromOne = previousOne + cost[top - 1];
16             long next = Math.min(fromTwo, fromOne);
17             previousTwo = previousOne;
18             previousOne = next;
19         }
20         return previousOne;
21     }
22     // Baseline: enumerate every continuation; only small arrays are practical.
23     public static long baseline(int[] cost) {
24         validate(cost);
25         return Math.min(walk(cost, 0), walk(cost, 1));
26     }
27     private static long walk(int[] cost, int step) {
28         if (step >= cost.length) return 0;
29         return (long) cost[step] + Math.min(walk(cost, step + 1), walk(cost, step + 2));
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
input
[2147483647,2147483647,2147483647,2147483647]
phase
"validated"
caseResults
[]
Both allowed starting destinations have zero arrival cost.
D(t) is cost to arrive before paying to depart. Top is n, beyond every charged stair. The two initial registers are zero even when no loop iteration is required.
input
[2147483647,2147483647,2147483647,2147483647]
phase
"range-start"
caseResults
[]
table
[0,0,null,null,null]
previousTwo
0
previousOne
0
position
1
Compare both complete incoming routes, including predecessor charges.
fromTwo=D(t−2)+cost[t−2]; fromOne=D(t−1)+cost[t−1]. Both registers are still old. No cost is charged at destination t itself.
input
[2147483647,2147483647,2147483647,2147483647]
phase
"candidate"
caseResults
[]
table
[0,0,null,null,null]
previousTwo
0
previousOne
0
position
2
two
2147483647
one
2147483647
next
2147483647
Store the minimum arrival cost and move the frontier.
The new pair is D(t−1), D(t). The reference retains no full table and never writes a cost entry. A tie needs no path preference for a value-only result.
input
[2147483647,2147483647,2147483647,2147483647]
phase
"commit"
caseResults
[]
table
[0,0,2147483647,null,null]
previousTwo
0
previousOne
2147483647
position
2
two
2147483647
one
2147483647
next
2147483647
Compare both complete incoming routes, including predecessor charges.
fromTwo=D(t−2)+cost[t−2]; fromOne=D(t−1)+cost[t−1]. Both registers are still old. No cost is charged at destination t itself.
input
[2147483647,2147483647,2147483647,2147483647]
phase
"candidate"
caseResults
[]
table
[0,0,2147483647,null,null]
previousTwo
0
previousOne
2147483647
position
3
two
2147483647
one
4294967294
next
2147483647
Store the minimum arrival cost and move the frontier.
The new pair is D(t−1), D(t). The reference retains no full table and never writes a cost entry. A tie needs no path preference for a value-only result.
input
[2147483647,2147483647,2147483647,2147483647]
phase
"commit"
caseResults
[]
table
[0,0,2147483647,2147483647,null]
previousTwo
2147483647
previousOne
2147483647
position
3
two
2147483647
one
4294967294
next
2147483647
Compare both complete incoming routes, including predecessor charges.
fromTwo=D(t−2)+cost[t−2]; fromOne=D(t−1)+cost[t−1]. Both registers are still old. No cost is charged at destination t itself.
input
[2147483647,2147483647,2147483647,2147483647]
phase
"candidate"
caseResults
[]
table
[0,0,2147483647,2147483647,null]
previousTwo
2147483647
previousOne
2147483647
position
4
two
4294967294
one
4294967294
next
4294967294
Store the minimum arrival cost and move the frontier.
The new pair is D(t−1), D(t). The reference retains no full table and never writes a cost entry. A tie needs no path preference for a value-only result.
input
[2147483647,2147483647,2147483647,2147483647]
phase
"commit"
caseResults
[]
table
[0,0,2147483647,2147483647,4294967294]
previousTwo
2147483647
previousOne
4294967294
position
4
two
4294967294
one
4294967294
next
4294967294
Return the arrival cost at the top position.
For n=0 or 1 a free start is already the top, so the empty loop returns zero. All shown long fixture values are exactly representable in JavaScript; upper-bound Java tests are separate.
input
[2147483647,2147483647,2147483647,2147483647]
phase
"range-complete"
caseResults
[]
table
[0,0,2147483647,2147483647,4294967294]
previousTwo
2147483647
previousOne
4294967294
position
4
answer
4294967294
Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
result
4294967294

Zero-price alternative

Input: [5,0,5,0] · Minimum departure cost to top: 0

Step 1 of 10: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

Minimum stair cost — pay at the predecessor

Phase: validated.

D(t) = min(D(t−2) + cost[t−2], D(t−1) + cost[t−1])

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Charged stairs — top is position n, beyond the last entry.

0: 5available in this pass
1: 0available in this pass
2: 5available in this pass
3: 0available in this pass

Top position 4 has no charge. Starting on position 0 or 1 costs zero before departure. D(t) is an arrival cost.

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
Variable	Value
input	`[5,0,5,0]`
phase	`"validated"`
caseResults	`[]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] cost) {
 6         Objects.requireNonNull(cost, "cost");
 7         if (cost.length > 100_000) throw new IllegalArgumentException("too many steps");
 8         for (int value : cost) if (value < 0) throw new IllegalArgumentException("negative cost");
 9     }
10     public static long minCostClimbingStairs(int[] cost) {
11         validate(cost);
12         long previousTwo = 0, previousOne = 0;
13         for (int top = 2; top <= cost.length; top++) {
14             long fromTwo = previousTwo + cost[top - 2];
15             long fromOne = previousOne + cost[top - 1];
16             long next = Math.min(fromTwo, fromOne);
17             previousTwo = previousOne;
18             previousOne = next;
19         }
20         return previousOne;
21     }
22     // Baseline: enumerate every continuation; only small arrays are practical.
23     public static long baseline(int[] cost) {
24         validate(cost);
25         return Math.min(walk(cost, 0), walk(cost, 1));
26     }
27     private static long walk(int[] cost, int step) {
28         if (step >= cost.length) return 0;
29         return (long) cost[step] + Math.min(walk(cost, step + 1), walk(cost, step + 2));
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
input
[5,0,5,0]
phase
"validated"
caseResults
[]
Both allowed starting destinations have zero arrival cost.
D(t) is cost to arrive before paying to depart. Top is n, beyond every charged stair. The two initial registers are zero even when no loop iteration is required.
input
[5,0,5,0]
phase
"range-start"
caseResults
[]
table
[0,0,null,null,null]
previousTwo
0
previousOne
0
position
1
Compare both complete incoming routes, including predecessor charges.
fromTwo=D(t−2)+cost[t−2]; fromOne=D(t−1)+cost[t−1]. Both registers are still old. No cost is charged at destination t itself.
input
[5,0,5,0]
phase
"candidate"
caseResults
[]
table
[0,0,null,null,null]
previousTwo
0
previousOne
0
position
2
two
5
one
0
next
0
Store the minimum arrival cost and move the frontier.
The new pair is D(t−1), D(t). The reference retains no full table and never writes a cost entry. A tie needs no path preference for a value-only result.
input
[5,0,5,0]
phase
"commit"
caseResults
[]
table
[0,0,0,null,null]
previousTwo
0
previousOne
0
position
2
two
5
one
0
next
0
Compare both complete incoming routes, including predecessor charges.
fromTwo=D(t−2)+cost[t−2]; fromOne=D(t−1)+cost[t−1]. Both registers are still old. No cost is charged at destination t itself.
input
[5,0,5,0]
phase
"candidate"
caseResults
[]
table
[0,0,0,null,null]
previousTwo
0
previousOne
0
position
3
two
0
one
5
next
0
Store the minimum arrival cost and move the frontier.
The new pair is D(t−1), D(t). The reference retains no full table and never writes a cost entry. A tie needs no path preference for a value-only result.
input
[5,0,5,0]
phase
"commit"
caseResults
[]
table
[0,0,0,0,null]
previousTwo
0
previousOne
0
position
3
two
0
one
5
next
0
Compare both complete incoming routes, including predecessor charges.
fromTwo=D(t−2)+cost[t−2]; fromOne=D(t−1)+cost[t−1]. Both registers are still old. No cost is charged at destination t itself.
input
[5,0,5,0]
phase
"candidate"
caseResults
[]
table
[0,0,0,0,null]
previousTwo
0
previousOne
0
position
4
two
5
one
0
next
0
Store the minimum arrival cost and move the frontier.
The new pair is D(t−1), D(t). The reference retains no full table and never writes a cost entry. A tie needs no path preference for a value-only result.
input
[5,0,5,0]
phase
"commit"
caseResults
[]
table
[0,0,0,0,0]
previousTwo
0
previousOne
0
position
4
two
5
one
0
next
0
Return the arrival cost at the top position.
For n=0 or 1 a free start is already the top, so the empty loop returns zero. All shown long fixture values are exactly representable in JavaScript; upper-bound Java tests are separate.
input
[5,0,5,0]
phase
"range-complete"
caseResults
[]
table
[0,0,0,0,0]
previousTwo
0
previousOne
0
position
4
answer
0
Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
result
0

Test the contract

Input: cost=[]
Output: 0
Top is the ground.
Input: cost=[7,8]
Output: 7
Depart cheaper free start and jump to top.
Input: cost=[0,0,0]
Output: 0
Zero-cost ties do not need a special greedy rule.
Input: cost=[5,0,5,0]
Output: 0
The free start and alternate charged stairs matter.
Input: cost=[-1]
Output: IllegalArgumentException
Validate before the short-array result.
Input: cost=null
Output: NullPointerException
Null is not an empty staircase.

Common mistakes and counterexamples

Return the cost at the last charged stair

Counterexample: [10,15,20] has top 3, while index 2 is still a charged stair.

Define the result at position n, with D(0)=D(1)=0.

Charge the destination or initialize D(1)=cost[1]

Counterexample: [10,15] should cost 10, but charging to arrive at start 1 can eliminate its free-start meaning.

Keep arrival-before-departure state and add the cost of the previous stair.

Take the cheaper of the next two prices greedily

Counterexample: From a fixed start 0, [0,1,2,100,1] tempts landing on price 1; the other landing leads directly past the expensive stair.

Evaluate the total continuation cost, not just the next local price. Compare both free starts at the full-problem level.

Use int or skip validation on a single stair

Counterexample: Four MAX_VALUE costs need 4294967294; [−1] must be rejected.

Accumulate in long and validate the entire array before shortcuts.

Follow-ups

Return one cheapest route.

Keep D and one chosen predecessor for each destination, with a deterministic tie policy. Backtrack from n to 0 or 1, reverse the visited stair indices, and separately identify which departures were charged. Reconstruction needs O(n) space/time in the worst case and should preserve the value-only API as a separate method.

Permit negative departure costs.

The exact-top prefix graph remains acyclic, so its recurrence still works with suitable numeric bounds. However, free-start bases need care: arriving at 1 via 0 could now cost less than starting at 1, so D(1)=min(0,cost[0]). The suffix baseline can retain its at-or-beyond-top base: an overshooting final jump from n−1 can be replaced with a one-step landing at n at the same departure cost. Recheck long bounds for signed sums and state the new semantics before changing validation.

Allow moves from a finite positive set instead of {1,2}.

Define the available free starts and exact top independently. For each destination, minimize D(t−d)+cost[t−d] over legal predecessor stairs and move sizes d. An unreachable sentinel may be necessary. Keep enough prior states for the largest move, and guard unreachable candidates before addition.

Related foundations

Dynamic programming: state before recurrence

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.