3693. Climbing Stairs II

Medium

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are standing at the bottom of a staircase that has n + 1 steps, numbered from 0 to n. You begin at step 0, and your goal is to reach the top step, which is step n.

You are given a 1-indexed integer array costs of length n, where costs[i] represents the cost associated with landing on step i. Note that step 0 (your starting point) has no cost.

From any step i, your movement is limited — you may only jump forward to one of the following three steps:

Step i + 1
Step i + 2
Step i + 3

Each jump has a price. The total cost of jumping from step i to step j is calculated as:

costs[j] + (j - i)²

This means every jump charges you two things:

The landing cost — costs[j], the cost of the step you land on.
The distance penalty — (j - i)², the square of how far you jumped. Longer jumps are more expensive: jumping 1 step adds 1, jumping 2 steps adds 4, and jumping 3 steps adds 9.

Starting from step 0 with a total cost of 0, you need to find the minimum total cost required to reach step n.

The challenge lies in balancing a trade-off: bigger jumps let you skip steps with high landing costs, but they incur larger distance penalties. Conversely, smaller jumps have cheap penalties but force you to pay for more steps along the way. Your task is to choose the sequence of jumps that minimizes the overall cost.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

The minimum cost to reach each step depends only on the three previous steps, a classic 1D DP with constant transitions.

Open in Flowchart

Intuition

The first thing to notice is that the cost of reaching any step depends only on where you came from, not on the entire path you took to get there. Whether you arrived at step 5 through a long winding route or a direct one, the only thing that matters going forward is the total cost accumulated so far. This is the classic hallmark of a problem suited for dynamic programming: optimal substructure with overlapping subproblems.

Let's think about what it takes to land on some step i. Since jumps can only cover a distance of 1, 2, or 3, the step right before i must have been one of exactly three candidates: i - 1, i - 2, or i - 3. There are no other possibilities.

So if we already knew the cheapest way to reach each of those three earlier steps, computing the cheapest way to reach step i becomes trivial — just try all three predecessors and pick whichever gives the smallest total:

Come from i - 1: pay its best cost, plus costs[i] + 1²
Come from i - 2: pay its best cost, plus costs[i] + 2²
Come from i - 3: pay its best cost, plus costs[i] + 3²

This naturally suggests defining f[i] as the minimum total cost to reach step i, and building the answer from the bottom up. We know the base case for free: f[0] = 0, since we start at step 0 with no cost.

A greedy approach (e.g., always taking the locally cheapest next jump) fails here because a cheap jump now might force expensive landings later, while paying a larger distance penalty up front could skip a very costly step. Only by tracking the best possible cost at every step do we guarantee that no beneficial combination of jumps is missed.

Once f is filled in from step 1 to step n, the value f[n] is exactly the minimum total cost to reach the top.

Solution Approach

Dynamic Programming

We use a one-dimensional DP array to track the minimum cost of reaching each step.

State definition

Let f[i] be the minimum total cost required to reach step i. The array has n + 1 entries, one for each step from 0 to n.

Initialization

f[0] = 0 — we start at step 0 for free.
All other entries are set to +∞ (inf), meaning "not yet reachable." Using infinity ensures that any real path found later will always be smaller and correctly overwrite it via min.

State transition

Step i can only be reached from steps i - 1, i - 2, or i - 3. Trying each valid predecessor j and adding the jump cost gives:

f[i] = min(f[j] + costs[i - 1] + (i - j)²) for j from i - 3 to i - 1

Here costs[i - 1] is the landing cost of step i (the array is 1-indexed in the problem but 0-indexed in code), and (i - j)² is the distance penalty. We must also guard against j < 0, since steps below 0 don't exist.

Final answer

After processing every step, f[n] holds the minimum cost to stand on the top step.

Code Walkthrough

class Solution:
    def climbStairs(self, n: int, costs: List[int]) -> int:
        n = len(costs)
        f = [inf] * (n + 1)
        f[0] = 0
        for i, x in enumerate(costs, 1):
            for j in range(i - 3, i):
                if j >= 0:
                    f[i] = min(f[i], f[j] + x + (i - j) ** 2)
        return f[n]

Step by step:

Setup: f = [inf] * (n + 1) creates the DP table, and f[0] = 0 sets the base case.
Outer loop: enumerate(costs, 1) iterates through the cost array while making i run from 1 to n, so i directly corresponds to the step number and x is the landing cost of that step. This avoids manual index arithmetic like costs[i - 1].
Inner loop: range(i - 3, i) enumerates the three possible predecessor steps i - 3, i - 2, and i - 1. The check if j >= 0 skips out-of-bounds predecessors (relevant only for the first couple of steps).
Relaxation: f[i] = min(f[i], f[j] + x + (i - j) ** 2) updates the best cost for step i — the accumulated cost at the predecessor, plus the landing cost x, plus the squared jump distance.
Result: f[n] is returned as the minimum total cost to reach the top.

Complexity Analysis

Time complexity: O(n) — each of the n steps examines at most 3 predecessors, a constant amount of work per step.
Space complexity: O(n) — for the DP array f. Since each state only depends on the previous three states, this could be reduced to O(1) by keeping just three rolling variables, though the array version is clearer.

Example Walkthrough

Let's trace the algorithm with costs = [5, 1, 4], meaning the staircase has steps 0 through 3, with landing costs:

Step	0	1	2	3
Landing cost	—	5	1	4

Initialization

f = [0, inf, inf, inf]

f[0] = 0 since we start at step 0 for free.

Step i = 1 (landing cost x = 5)

Possible predecessors are j ∈ {-2, -1, 0}, but only j = 0 is valid:

From j = 0: f[0] + 5 + (1 - 0)² = 0 + 5 + 1 = 6

f = [0, 6, inf, inf]

Step i = 2 (landing cost x = 1)

Valid predecessors are j = 0 and j = 1:

From j = 0: f[0] + 1 + (2 - 0)² = 0 + 1 + 4 = 5
From j = 1: f[1] + 1 + (2 - 1)² = 6 + 1 + 1 = 8

The direct 2-step jump wins despite its larger distance penalty, because it skips step 1's expensive landing cost of 5:

f = [0, 6, 5, inf]

Step i = 3 (landing cost x = 4)

All three predecessors j = 0, 1, 2 are valid:

From j = 0: f[0] + 4 + (3 - 0)² = 0 + 4 + 9 = 13
From j = 1: f[1] + 4 + (3 - 1)² = 6 + 4 + 4 = 14
From j = 2: f[2] + 4 + (3 - 2)² = 5 + 4 + 1 = 10

f = [0, 6, 5, 10]

Result

f[3] = 10, achieved by the path 0 → 2 → 3:

Jump 0 → 2: cost 1 + 2² = 5
Jump 2 → 3: cost 4 + 1² = 5
Total: 10

This example highlights the core trade-off: the one-big-jump path 0 → 3 avoids all intermediate landing costs but pays a hefty 9 distance penalty (total 13), while the all-small-jumps path 0 → 1 → 2 → 3 pays minimal penalties but gets stuck with step 1's costly landing (total 14). The DP correctly identifies the middle ground — jumping over the expensive step 1, then taking a cheap single step — as the optimal route.

Solution Implementation

1class Solution:
2    def climbStairs(self, n: int, costs: List[int]) -> int:
3        # Use the length of costs as the total number of stairs
4        num_stairs = len(costs)
5
6        # dp[i] represents the minimum total cost to reach stair i
7        # Initialize all values to infinity, except the starting point (ground, stair 0)
8        dp = [inf] * (num_stairs + 1)
9        dp[0] = 0
10
11        # Iterate over each stair (1-indexed) along with its cost
12        for i, cost in enumerate(costs, 1):
13            # From stair j, we can jump to stair i if i - j is at most 3,
14            # so consider the three previous positions: i-3, i-2, i-1
15            for j in range(i - 3, i):
16                # Make sure the previous position is valid (not below ground)
17                if j >= 0:
18                    # Transition: cost to reach j, plus the cost of stair i,
19                    # plus the squared distance penalty (i - j)^2
20                    dp[i] = min(dp[i], dp[j] + cost + (i - j) ** 2)
21
22        # The answer is the minimum cost to reach the top stair
23        return dp[num_stairs]
24

1class Solution {
2    public int climbStairs(int n, int[] costs) {
3        // dp[i] represents the minimum total cost to reach step i
4        int[] dp = new int[n + 1];
5
6        // Use a large value (half of MAX_VALUE to avoid overflow when adding)
7        // to represent an unreachable / uncomputed state
8        final int INF = Integer.MAX_VALUE / 2;
9        Arrays.fill(dp, INF);
10
11        // Base case: standing at step 0 (the ground) costs nothing
12        dp[0] = 0;
13
14        // Compute the minimum cost for each step from 1 to n
15        for (int i = 1; i <= n; ++i) {
16            // Cost of landing on step i (costs array is 0-indexed)
17            int stepCost = costs[i - 1];
18
19            // From a previous step j, we can jump 1, 2, or 3 steps to reach i,
20            // so j ranges from max(0, i - 3) to i - 1
21            for (int j = Math.max(0, i - 3); j < i; ++j) {
22                // Total cost = cost to reach step j
23                //            + cost of landing on step i
24                //            + penalty equal to the square of the jump distance
25                dp[i] = Math.min(dp[i], dp[j] + stepCost + (i - j) * (i - j));
26            }
27        }
28
29        // Minimum cost to reach the top step n
30        return dp[n];
31    }
32}
33

1class Solution {
2public:
3    int climbStairs(int n, vector<int>& costs) {
4        // minCost[i] represents the minimum total cost to reach step i.
5        // Initialize all entries with a large sentinel value (INT_MAX / 2)
6        // to avoid integer overflow when adding costs during transitions.
7        vector<int> minCost(n + 1, INT_MAX / 2);
8
9        // Base case: standing at the ground (step 0) costs nothing.
10        minCost[0] = 0;
11
12        // Compute the minimum cost for each step from 1 to n.
13        for (int i = 1; i <= n; ++i) {
14            // Cost associated with landing on step i (1-indexed step,
15            // 0-indexed array).
16            int stepCost = costs[i - 1];
17
18            // From step j, we can jump to step i if the jump length
19            // (i - j) is at most 3. So j ranges over the previous
20            // three steps (clamped at 0).
21            for (int j = max(0, i - 3); j < i; ++j) {
22                int jumpLength = i - j;
23
24                // Transition: total cost = cost to reach step j
25                //                        + cost of landing on step i
26                //                        + square of the jump length.
27                minCost[i] = min(minCost[i],
28                                 minCost[j] + stepCost + jumpLength * jumpLength);
29            }
30        }
31
32        // The answer is the minimum cost to reach the top step n.
33        return minCost[n];
34    }
35};
36

1/**
2 * Calculates the minimum total cost to climb to the n-th step.
3 * From any step, you may jump up 1, 2, or 3 steps at a time.
4 * Landing on step i costs: costs[i - 1] + (jump distance)^2.
5 *
6 * Dynamic programming approach:
7 *   f[i] = minimum cost to reach step i
8 *   Transition: f[i] = min(f[j] + costs[i - 1] + (i - j)^2) for j in [i - 3, i - 1]
9 *
10 * @param n     The target step number (1-indexed)
11 * @param costs The cost array, where costs[i - 1] is the base cost of landing on step i
12 * @returns     The minimum total cost to reach step n
13 */
14function climbStairs(n: number, costs: number[]): number {
15    // Use a large value as "infinity" to represent unreachable states.
16    // Divide by 2 to avoid overflow when adding costs.
17    const INF: number = Number.MAX_SAFE_INTEGER / 2;
18
19    // f[i] represents the minimum cost to reach step i.
20    const f: number[] = Array(n + 1).fill(INF);
21
22    // Base case: starting at the ground (step 0) costs nothing.
23    f[0] = 0;
24
25    // Compute the minimum cost for each step from 1 to n.
26    for (let i = 1; i <= n; ++i) {
27        // Base cost of landing on step i.
28        const cost: number = costs[i - 1];
29
30        // Try jumping to step i from steps i-1, i-2, and i-3 (if valid).
31        for (let j = Math.max(0, i - 3); j < i; ++j) {
32            const jump: number = i - j;
33            // Total cost = cost to reach step j + landing cost + squared jump distance.
34            f[i] = Math.min(f[i], f[j] + cost + jump * jump);
35        }
36    }
37
38    // The answer is the minimum cost to reach step n.
39    return f[n];
40}
41

Time and Space Complexity

Time Complexity: O(n), where n is the number of stairs (i.e., len(costs)). The outer loop iterates over all n stairs, and for each stair i, the inner loop checks at most 3 previous positions (i - 3 to i - 1), which is a constant amount of work. Therefore, the total time is O(3n) = O(n).
Space Complexity: O(n). The algorithm maintains a dynamic programming array f of size n + 1 to store the minimum cost of reaching each stair, and no other data structure grows with the input size.

Common Pitfalls

1. Omitting the `j >= 0` boundary guard — Python's negative indexing hides the bug

This is the most insidious pitfall for this problem, because Python does not throw an error for negative indices.

The buggy version:

for i, cost in enumerate(costs, 1):
    for j in range(i - 3, i):          # j can be -2, -1 when i = 1 or 2
        dp[i] = min(dp[i], dp[j] + cost + (i - j) ** 2)

When i = 1, the inner loop produces j = -2, -1, 0. In most languages this crashes immediately with an out-of-bounds error, making the mistake easy to catch. In Python, however, dp[-1] silently reads the last element of the array and dp[-2] reads the second-to-last — which are positions n and n - 1, exactly the states we have not computed yet.

Why it often goes unnoticed: at the time i = 1 and i = 2 are processed, dp[-1] and dp[-2] still hold inf, so min discards them and the answer happens to be correct for this particular forward iteration order. The code passes tests, but it is fragile:

If someone refactors to a different initialization (e.g., dp = [0] * (n + 1) plus explicit relaxation), dp[-1] = 0 becomes a phantom "free path" wrapping around from the top of the staircase, producing answers that are far too small.
If the iteration order changes, or the rolling-variable space optimization is applied carelessly, the stale values become real garbage inputs.

The fix: always validate the predecessor explicitly, either with the guard shown in the correct code:

for j in range(i - 3, i):
    if j >= 0:
        dp[i] = min(dp[i], dp[j] + cost + (i - j) ** 2)

or by clamping the range so negative indices can never be generated:

for j in range(max(0, i - 3), i):
    dp[i] = min(dp[i], dp[j] + cost + (i - j) ** 2)

The max(0, i - 3) variant is slightly cleaner since it removes the conditional from the loop body entirely.

2. Off-by-one confusion between the 1-indexed `costs` and the 0-indexed DP array

The problem states costs is 1-indexed (costs[i] is the cost of step i), but the Python list is 0-indexed. Mixing these up leads to:

# WRONG: pays the cost of the *next* step when landing on step i
dp[i] = min(dp[i], dp[j] + costs[i] + (i - j) ** 2)   # IndexError at i = n, or shifted costs

Two clean ways to avoid this:

Use enumerate(costs, 1) as the solution does, so i is the step number and cost is already the correct landing cost — no manual i - 1 arithmetic anywhere.
If indexing manually, consistently write costs[i - 1] for step i and verify with a tiny example (n = 1) that dp[1] = costs[0] + 1.

3. Charging the cost at the wrong moment (departure vs. landing)

Solvers who have done LeetCode 746 Min Cost Climbing Stairs often carry over its model, where you pay cost[i] when leaving step i. Here the rules are different: you pay costs[j] when landing on step j, step 0 is free, and step n's cost is included. Transplanting the 746 transition gives a formula like dp[i] = min(dp[i-1] + cost[i-1], ...) that double-counts or skips the final step's cost. Always re-derive the transition from this problem's cost definition: jump cost = costs[j] + (j - i)².

4. Attempting a greedy strategy instead of DP

It is tempting to reason locally — "always jump 3 to skip expensive steps" or "always take the cheapest immediate jump." Both fail. Consider costs = [1, 100, 1]: jumping 0 → 1 → 3 costs 1 + 1 + 1 + 4 = 7, while the greedy "skip the expensive middle with one big jump" 0 → 3 costs 1 + 9 = 10, and the locally-cheapest-first strategy can be misled the other way with different values. The squared distance penalty interacts non-locally with the landing costs, so only exploring all three predecessors per step (the DP relaxation) guarantees optimality.

5. Initializing the DP array with `0` instead of `inf`

dp = [0] * (n + 1)   # WRONG

With zeros everywhere, min(dp[i], ...) compares real path costs against a fake "free" cost of 0, and every entry stays 0. The inf initialization encodes "unreachable until proven otherwise," which is what makes the min relaxation sound. (This pitfall also amplifies Pitfall #1: with zero-initialization, dp[-1] is 0 rather than inf, and the wrap-around bug becomes fully visible.)

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know