Module 2 · 1D Dynamic Programming

Min Cost Climbing Stairs

EasyProblem 3 of 30 8 min read ~17 min to solve LeetCode

Dynamic Programming1D DPArrayMinimization

Asked atAmazonGoogleMicrosoftAdobeApple

Problem Statement

You are given an integer array cost where cost[i] is the cost of stepping on stair i. After paying the cost for a stair, you may climb either 1 or 2 steps. You may start from stair 0 or stair 1. Return the minimum cost to reach the top, which is just beyond the last stair.

Input

An integer array cost, where each value is the cost of landing on that stair.

Output

An integer: the minimum total cost required to reach the top beyond the final stair.

Constraints

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

Examples

Example 1

Input:

cost = [10,15,20]

Output: 15

Explanation: Start at stair 1, pay 15, then take a 2-step to the top.

Example 2

Input:

cost = [1,100,1,1,1,100,1,1,100,1]

Output: 6

Explanation: The cheapest route pays the low-cost stairs and avoids the expensive 100-cost stairs where possible.

Learning Objectives

Turn a path-counting staircase recurrence into a minimum-cost recurrence.
Define state as the best cost to land on a stair, not the best cost after leaving it.
Use the top position as a final choice between the last two reachable stairs.
Compress the 1D minimum table to two rolling values.

Intuition

The top has no cost, so the important question is the minimum cost to stand on each real stair. To land on stair i, your previous stair was either i - 1 or i - 2. You must pay cost[i] when you land, so the best cost for i is its own cost plus the cheaper of those two previous best costs.

At the end, you do not have to land on a special top stair. You can jump to the top from either of the last two stairs, and jumping itself is free. That is why the answer is the minimum of the final two stair states.

Common mistakes

×Treating the top as if it has the same cost as the last stair.
×Returning only the cost to land on the last stair, even though the second-to-last stair can jump directly to the top.
×Forgetting that you may start at stair 0 or stair 1.
×Using the climbing-stairs counting base cases instead of cost-based base cases.

State Definition

Let dp[i] be the minimum total cost required to land on stair i. The final answer is min(dp[n - 1], dp[n - 2]) because the top can be reached from either of the last two stairs.

State Transition

To land on stair i, come from i - 1 or i - 2, then pay cost[i]:

dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]) for i >= 2.

Base cases are the costs of choosing the starting stair: dp[0] = cost[0] and dp[1] = cost[1].

Solutions

Solution: Bottom-up with two rolling costs

The recurrence only needs the previous two landing costs. Store dp[i - 2] and dp[i - 1], compute the current landing cost, and roll the window forward.

Step-by-step

Seed twoStepsBack with cost[0] and oneStepBack with cost[1].
For each stair from index 2 to the end, compute the minimum cost to land there.
Shift the two rolling values after each stair.
Return min(oneStepBack, twoStepsBack) because the top is reachable from either of the final two stairs.

Time

O(n)

Space

O(1)

Each stair is processed once and only two previous costs are stored.

Java implementation

Loading…

Dry Run

Sample input

cost = [1,100,1,1,1,100,1,1,100,1]. Start with dp[0] = 1 and dp[1] = 100.

step	cost[step]	twoStepsBack before	oneStepBack before	current cost to land
2	1	1	100	2
3	1	100	2	3
4	1	2	3	3
5	100	3	3	103
6	1	3	103	4
7	1	103	4	5
8	100	4	5	104
9	1	5	104	6

After the last stair, the final two landing costs are 104 and 6. The top is free to enter from either, so the answer is 6.

Complexity Analysis

This is a minimum version of the Climbing Stairs recurrence, with the same O(n) time and O(1) space after compression.

Bottom-up with two rolling costs