LeetCode 3693 - Climbing Stairs II

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem is an extension of the classic "climbing stairs" dynamic programming problem but with more complex jump costs. You are given a staircase with n + 1 steps, numbered from 0 to n. Each intermediate step i (1-indexed) has an associated cost costs[i]. You start at step 0 with zero cost. From any step i, you can jump forward 1, 2, or 3 steps. The cost of a jump from step i to step j is costs[j] + (j - i)^2. Your goal is to find the minimum total cost to reach the final step n.

The input costs is a 1-indexed array of length n, so costs[1] corresponds to step 1. The output is an integer representing the minimal cumulative cost to reach step n using optimal jumps.

Constraints give 1 <= n <= 10^5 and 1 <= costs[i] <= 10^4. This indicates that a brute-force recursion that explores all possible paths would be too slow due to exponential growth in options. We need a solution that is linear or near-linear in n. Important edge cases include n = 1 (smallest staircase), high costs that make certain jumps suboptimal, and situations where skipping steps is cheaper due to the quadratic jump cost.

Approaches

A brute-force approach would attempt every possible sequence of jumps from step 0 to step n. At each step, you recursively calculate the cost for jumps of 1, 2, or 3 steps ahead and select the minimum. While this guarantees correctness because it explores all paths, it is infeasible for large n because the number of sequences grows exponentially.

The key observation for an optimal solution is that the minimum cost to reach step i depends only on the minimum costs to reach the previous three steps. This allows us to use dynamic programming. We define dp[i] as the minimum cost to reach step i. The recurrence is:

dp[i] = min(
    dp[i-1] + costs[i] + 1^2,
    dp[i-2] + costs[i] + 2^2,
    dp[i-3] + costs[i] + 3^2
)

We initialize dp[0] = 0 and compute dp[1] through dp[n] iteratively.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(3^n)	O(n)	Recursively try all jump sequences
Optimal DP	O(n)	O(n)	Iteratively compute minimal cost using previous 3 steps

Algorithm Walkthrough

Initialize a dynamic programming array dp of size n + 1, where dp[i] will store the minimum cost to reach step i. Set dp[0] = 0 because starting from step 0 has zero cost.
For each step i from 1 to n, compute the minimum cost to reach it by considering jumps from steps i-1, i-2, and i-3. Only include jumps that are valid (i.e., i - j >= 0).
For each valid previous step j, calculate the jump cost as dp[j] + costs[i] + (i - j)^2 and update dp[i] with the minimum value among these options.
After iterating through all steps, the minimum cost to reach step n is stored in dp[n]. Return this value.

Why it works: The recurrence relation guarantees that at each step i, we compute the minimum possible cost using the already computed minimum costs of previous steps. Since each step depends only on the previous three steps, this ensures optimal substructure. The algorithm explores all possible jump combinations in a cumulative way without recomputation, ensuring correctness.

Python Solution

from typing import List

class Solution:
    def climbStairs(self, n: int, costs: List[int]) -> int:
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            min_cost = float('inf')
            for j in range(1, 4):
                if i - j >= 0:
                    min_cost = min(min_cost, dp[i - j] + costs[i - 1] + j * j)
            dp[i] = min_cost
        return dp[n]

Implementation walkthrough: The DP array dp stores minimum costs. For each step i, we iterate over possible jumps from 1 to 3 steps back. The expression dp[i - j] + costs[i - 1] + j * j correctly calculates the cumulative cost including the quadratic jump cost. Using costs[i - 1] accounts for 1-indexing in the problem description. Finally, dp[n] contains the minimum cost to reach the last step.

Go Solution

import "math"

func climbStairs(n int, costs []int) int {
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        minCost := math.MaxInt64
        for j := 1; j <= 3; j++ {
            if i-j >= 0 {
                cost := dp[i-j] + costs[i-1] + j*j
                if cost < minCost {
                    minCost = cost
                }
            }
        }
        dp[i] = minCost
    }
    return dp[n]
}

Go-specific notes: Go requires explicit handling of MaxInt64 for initial minimum cost comparison. The slice dp is used similarly to the Python list. Integer overflow is not an issue with the given constraints.

Worked Examples

Example 1: n = 4, costs = [1,2,3,4]

i	dp[i-1] + jump1	dp[i-2] + jump2	dp[i-3] + jump3	dp[i]
1	0 + 1 + 1	-	-	2
2	2 + 2 + 1	0 + 2 + 4	-	3
3	3 + 3 + 1	2 + 3 + 4	0 + 3 + 9	6
4	6 + 4 + 1	3 + 4 + 4	2 + 4 + 9	13

Example 2: n = 4, costs = [5,1,6,2]

i	dp[i-1] + jump1	dp[i-2] + jump2	dp[i-3] + jump3	dp[i]
1	0 + 5 + 1	-	-	6
2	6 + 1 + 1	0 + 1 + 4	-	5
3	5 + 6 + 1	6 + 6 + 4	0 + 6 + 9	12
4	12 + 2 + 1	5 + 2 + 4	6 + 2 + 9	11

Example 3: n = 3, costs = [9,8,3]

i	dp[i-1] + jump1	dp[i-2] + jump2	dp[i-3] + jump3	dp[i]
1	0 + 9 + 1	-	-	10
2	10 + 8 + 1	0 + 8 + 4	-	8
3	8 + 3 + 1	10 + 3 + 4	0 + 3 + 9	12

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each step computes the minimum from at most 3 previous steps, iterating through n steps
Space	O(n)	DP array of size n + 1 is required to store intermediate minimum costs

The linear time complexity is justified because each step performs a constant number of operations. Space can be further optimized to O(1) by keeping only the last three DP values at each iteration.

Test Cases

# provided examples
assert Solution().climbStairs(4, [1,2,3,4]) == 13  # Example 1
assert Solution().climbStairs(4, [5,1,6,2]) == 11  # Example 2
assert Solution().climbStairs(3, [9,8,3]) == 12    # Example 3

# edge cases
assert Solution().climbStairs(1, [10]) == 11       # smallest n, single step
assert Solution().climbStairs(2, [1,1]) == 3      # minimal costs, simple jump
assert Solution().