Min Cost Climbing Stairs
Find the cheapest way to the top of a staircase where every step you stand on has a price.
Each step of a staircase has a price, given in an array costcost[i]
Example 1
Output: 15
Explanation: start on step 1, pay 15, climb two steps to the top.
Example 2
Output: 6
Explanation: stand on steps 0, 2, 4, 6, 7 and 9, which avoids every 100.
The Idea
Picture a staircase where every step asks for a fee when you stand on it, and the landing at the top is free. You may take the steps one at a time or skip one, and you want to arrive at the top having paid as little as possible.
In Example 1 the staircase has three steps, with prices 10, 15 and 20, so the top is step 3. Starting on step 0 and standing on every step costs 10 + 15 + 20 = 45. Starting on step 0 and skipping to step 2 costs 10 + 20 = 30. Starting on step 1 costs only 15, because two steps up from step 1 is already the top.
With three steps there are only a few routes to compare. Example 2 has ten steps and far more routes. So how do we find the cheapest route without trying them all?
Turn the question around. Instead of following routes upward, ask about one step at a time: what is the least you must have paid to stand on step i, before paying its own price? Call that the cheapest cost to stand on step i. For step 0 and step 1 it is 0, since you may start there. Any higher step is reached from one or two steps below it. So its cheapest cost is the smaller of two sums: the step below's cheapest cost plus that step's price, or the same for the step two below.
Look at the picture below, which fills in these cheapest costs for Example 1.
The bottom row, labelled "cheapest cost to stand here, before paying", starts with 0 and 0 for step 0 and step 1. Step 2 can be reached from step 1 for 0 + 15 = 15, or from step 0 for 0 + 10 = 10, so its box holds 10. For the top, the orange arrow from step 1 costs 0 + 15 = 15 and the dashed arrow from step 2 costs 10 + 20 = 30. The top's box holds the smaller sum, 15, which is the answer.
So each step's cheapest cost needs only the two values just below it, and each value is worked out once. Building the top's answer this way, from a table of stored answers for the lower steps, is called dynamic programming.
Solution Approach
A method that tries every route gets the right answer but is slow, and the table avoids that. Turning the table into code means settling four things: what one entry holds, how it follows from the two below, where the table starts, and how much to keep.
Trying every route
What happens if we skip the table? A method can work out the cheapest cost to stand on step i by calling itself for step i - 1 and step i - 2. Those calls call themselves again, down to step 0 and step 1. It gives the right answers, but the same lower steps are worked out over and over. For the ten steps of Example 2 it makes 177 calls. For 30 steps it makes 2,692,537 calls, and for 40 steps 331,160,281.
What one entry means
What should the table store? Write dp[i]cost[i]cost.lengthdp[n]
From two entries to the next
How does dp[i]cost[i - 1]cost[i - 2]dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
Where the table starts
Which entries need no rule? Step 0 and step 1 are free starting places, so dp[0] = dp[1] = 0dp[10]
Keeping only two numbers
Do we need the whole table? The rule for step i reads only dp[i - 1]dp[i - 2]
Java Solution
The method minCostClimbingStairs
- First, set
andtwoBelow to 0. They start as the cheapest costs to stand on step 0 and step 1, which are both free.oneBelow - A loop moves
from step 2 up toi , the top. The condition iscost.length , so the last pass works out the top itself.i <= cost.length - Inside the loop,
gets the cheapest cost to stand on step i: the smaller ofhere andoneBelow + cost[i - 1] .twoBelow + cost[i - 2] - Then both variables move up one step:
takes the value oftwoBelow , andoneBelow takesoneBelow .here - When the loop ends,
holds the cheapest cost to stand on the top, and the method returns it.oneBelow
The main
public class MinCostClimbingStairs {
public static int minCostClimbingStairs(int[] cost) {
int twoBelow = 0; // cheapest cost to stand on step 0
int oneBelow = 0; // cheapest cost to stand on step 1
for (int i = 2; i <= cost.length; i++) { // step cost.length is the top
int here = Math.min(oneBelow + cost[i - 1], twoBelow + cost[i - 2]);
twoBelow = oneBelow;
oneBelow = here;
}
return oneBelow;
}
public static void main(String[] args) {
System.out.println(minCostClimbingStairs(new int[] {10, 15, 20}));
System.out.println(minCostClimbingStairs(new int[] {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));
System.out.println(minCostClimbingStairs(new int[] {5, 3}));
System.out.println(minCostClimbingStairs(new int[] {4, 4, 4, 4}));
}
}
Running it prints:
15
6
3
8
The 15 and the 6 match the answers of Example 1 and Example 2. The 3 comes from [5, 3]
Look at the last line, 8. With four steps that all cost 4, the cheapest route skips every other step and pays twice, for example on step 1 and step 3. The table behind it reads 0, 0, 4, 4, 8.
The <=i < cost.length
The original implementation,
Complexity
The work is one climb up the stairs, with the same small amount of work on each step.
- Time: O(n), because the loop runs once for every place from step 2 to the top, n - 1 times for n prices, with two additions and one
each time.Math.min - Space: O(1), because only
,twoBelow andoneBelow are kept however long the staircase is, while a full table would hold n + 1 entries.here
The same pattern of choosing between the two previous entries appears in