3693. Climbing Stairs II

2026, Nov 09 2 mins read

1. Description

A staircase has steps numbered 0 through n. You start at step 0 with no cost.
The array costs has length n, where costs[j - 1] is the landing cost for step j.
Each jump moves forward by 1, 2, or 3 steps. Jumping from step i to step j costs costs[j - 1] + (j - i)$^2$.
Return the minimum total cost to reach step n.

2. Example

Example 1

Input: n = 4, costs = [1,2,3,4]
Output: 13
Explanation: The path 0 → 1 → 2 → 4 costs 2 + 3 + 8 = 13.

Example 2

Input: n = 4, costs = [5,1,6,2]
Output: 11
Explanation: The path 0 → 2 → 4 costs 5 + 6 = 11.

Example 3

Input: n = 3, costs = [9,8,3]
Output: 12
Explanation: Jumping directly from step 0 to step 3 costs 3 + 9 = 12.

3. Constraints

1 <= n == costs.length <= 10$^5$
1 <= costs[i] <= 10$^4$

4. Solutions

Dynamic Programming

n = costs.size()
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int climbStairs(int n, vector<int> &costs) {
        vector<int> min_costs{0};
        if (n >= 1) {
            min_costs.push_back(costs[0] + 1);
        }

        if (n >= 2) {
            min_costs.push_back(costs[1] + min(4, min_costs[1] + 1));
        }

        if (n >= 3) {
            min_costs.push_back(costs[2] + min({9, min_costs[1] + 4, min_costs[2] + 1}));
        }

        if (n >= 4) {
            for (int i = 4; i <= n; ++i) {
                min_costs[0] = min_costs[1];
                min_costs[1] = min_costs[2];
                min_costs[2] = min_costs[3];

                min_costs[3] =
                    costs[i - 1] + min({min_costs[0] + 9, min_costs[1] + 4, min_costs[2] + 1});
            }
        }

        return min_costs.back();
    }
};

Search

Tags