Climb with step costs · DSA Mastery

Scenario

A maps app plans walking routes through a metro station. One exit is a staircase, and each stair has an effort score. A walker starts on the ground at the bottom.

Each move climbs one stair or two stairs. Landing on a stair costs its effort. The top landing, above the last stair, costs nothing.

Your team lead asks: "What is the least total effort needed to get from the ground to the top landing?"

Your task

Write least_effort_to_the_top(effort).

effort[i] is the effort of landing on stair i. The stairs are numbered from 0.
The walker starts on the ground, below stair 0. One move climbs one stair or two stairs.
The walker is done when a move reaches the top landing, which is one stair above the last stair, or goes past it. So a move from the last stair or from the stair before it can finish.
Return the least total effort of the stairs the walker lands on.

Examples

Example 1 (traced)#

text2 lines

Input:  effort = [4, 2, 7, 1, 6]
Output: 3

Let best[i] be the least effort to be standing on stair i. Stair i is reached from the stair below it or the stair two below it, and the ground counts as a stair that costs nothing. So best[i] = effort[i] + min(best[i - 1], best[i - 2]).

Stair	Effort	Reached from	best
ground	0	start	0
0	4	the ground	4 + 0 = 4
1	2	the ground (two stairs at once)	2 + 0 = 2
2	7	stair 1 (best 2) or stair 0 (best 4)	7 + 2 = 9
3	1	stair 2 (best 9) or stair 1 (best 2)	1 + 2 = 3
4	6	stair 3 (best 3) or stair 2 (best 9)	6 + 3 = 9

The top landing is reached from stair 4 or stair 3. The cheaper is min(9, 3) = 3. The walker lands on stairs 1 and 3, then jumps from stair 3 over stair 4 to the top.

Example 2#

text2 lines

Input:  effort = [7]
Output: 0

From the ground, one move of two stairs reaches the top landing. The walker never lands on stair 0.

Example 3#

text2 lines

Input:  effort = [1, 2, 100, 3]
Output: 5

The best way lands on stairs 1 and 3 for 2 + 3 = 5. Choosing the cheaper of the next two stairs at every move costs 6: stair 0, then stair 1, then stair 3.

Constraints

1 ≤ len(effort) ≤ 100,000
0 ≤ effort[i] ≤ 1000

What does n ≤ 100000 tell you?

There can be 100,000 stairs. The number of different ways to climb them grows by about 1.6 times with every extra stair, so trying every way is impossible. A table with one entry for each stair costs 100,000 small steps.

Scenario

A maps app plans walking routes through a metro station. One exit is a staircase, and each stair has an effort score. A walker starts on the ground at the bottom.

Each move climbs one stair or two stairs. Landing on a stair costs its effort. The top landing, above the last stair, costs nothing.

Your team lead asks: "What is the least total effort needed to get from the ground to the top landing?"

Your task

Write least_effort_to_the_top(effort).

effort[i] is the effort of landing on stair i. The stairs are numbered from 0.
The walker starts on the ground, below stair 0. One move climbs one stair or two stairs.
The walker is done when a move reaches the top landing, which is one stair above the last stair, or goes past it. So a move from the last stair or from the stair before it can finish.
Return the least total effort of the stairs the walker lands on.

Examples

Example 1 (traced)#

text2 lines

Input:  effort = [4, 2, 7, 1, 6]
Output: 3

Stair	Effort	Reached from	best
ground	0	start	0
0	4	the ground	4 + 0 = 4
1	2	the ground (two stairs at once)	2 + 0 = 2
2	7	stair 1 (best 2) or stair 0 (best 4)	7 + 2 = 9
3	1	stair 2 (best 9) or stair 1 (best 2)	1 + 2 = 3
4	6	stair 3 (best 3) or stair 2 (best 9)	6 + 3 = 9

The top landing is reached from stair 4 or stair 3. The cheaper is min(9, 3) = 3. The walker lands on stairs 1 and 3, then jumps from stair 3 over stair 4 to the top.

Example 2#

text2 lines

Input:  effort = [7]
Output: 0

From the ground, one move of two stairs reaches the top landing. The walker never lands on stair 0.

Example 3#

text2 lines

Input:  effort = [1, 2, 100, 3]
Output: 5

The best way lands on stairs 1 and 3 for 2 + 3 = 5. Choosing the cheaper of the next two stairs at every move costs 6: stair 0, then stair 1, then stair 3.

Constraints

1 ≤ len(effort) ≤ 100,000
0 ≤ effort[i] ≤ 1000

What does n ≤ 100000 tell you?