Skip to main content

Staircase Token Pairs

easy
Dynamic ProgrammingArrayDp 1d
Asked atAmazonGoogleMicrosoft

Problem Description

You are given an array `stepCost` where `stepCost[i]` represents the cost of stepping on stair `i`. Once you pay the cost, you may climb one or two steps forward.

You may start from index `0` or index `1`. Your goal is to reach the top of the staircase (beyond the last index).

Return the minimum total cost to reach the top.

**Example 1:**
```
Input: stepCost = [3, 2, 5, 1, 4]
Output: 6
Explanation: Start at index 1 (cost 2), jump to index 3 (cost 1), jump to index 5 (top). Total = 3.
Wait — start at index 1 (cost 2), step to index 3 (cost 1), step to index 5 which is top. Total cost = 3. Or start at 0 (cost 3), step to 2 (cost 5)... Let's recount: start index 1 cost=2, jump two to index 3 cost=1, jump two to top (index 5). Total = 2+1=3. But let's pick a clearer path: start 0 (cost 3), jump two to index 2 (cost 5)? No. Correct answer = 6: indices 0→2→4 gives 3+5+4=12; indices 1→3 gives 2+1=3 then top. Actually output is 3.
```

**Example 1 (corrected):**
```
Input: stepCost = [3, 2, 5, 1, 4]
Output: 3
Explanation: Start at index 1 (cost 2), jump two steps to index 3 (cost 1), jump two steps to the top. Total = 2 + 1 = 3.
```

**Example 2:**
```
Input: stepCost = [6, 4, 3, 8, 2, 7]
Output: 9
Explanation: Start at index 0 (cost 6), jump two to index 2 (cost 3), jump two to index 4 (cost 2), jump two to top. Total = 6 + 3 = 9. Or 4+3+2=9 starting at 1.
```

Constraints

  • 2 <= stepCost.length <= 1000
  • 0 <= stepCost[i] <= 999

Follow-up

Extend the problem so you can jump up to K steps at once instead of just 1 or 2. How does the recurrence change and what is the new time complexity?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.