Sweaty Imposter

Min Cost Climbing Stairs

EasyDynamic Programming (1-D & 2-D)NeetCode 150JuniorOpen on LeetCodeUpdated

You're given an array cost where cost[i] is the price of stepping off stair i. After paying it, you can climb one or two stairs. You may start on stair 0 or stair 1 for free. Return the minimum total cost to reach the top, which is the position just past the last stair.

Examples

cost = [4,9,3] returns 7

Start on stair 0, pay 4 to jump to stair 2, then pay 3 to reach the top.

cost = [2,2,8,1,6,1] returns 4

Start on stair 1 and pay 2, 1, and 1 at stairs 1, 3, and 5, jumping two each time and skipping the expensive stairs.

cost = [7,7] returns 7

From either stair, one payment of 7 and a jump reach the top.

Constraints

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

Hints

Hint 1

To reach any position, where could your last step have come from?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Let dp[i] be the cheapest way to stand on position i, with dp[0] = dp[1] = 0 because you may start on either. You arrive at i from i - 1 after paying cost[i - 1], or from i - 2 after paying cost[i - 2], so dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]). The answer is dp[n], the top. Only the last two values are needed: O(n) time, O(1) space.

Time

O(n)

Space

O(1)

Pitfall

Returning the cost to stand on the last stair. The top is one position past it, so the answer is dp[n], and the last stair's own cost only counts if you step off from it.

Solutions

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int prevPrev = 0, prev = 0;
        for (int i = 2; i <= cost.length; i++) {
            int cur = Math.min(prev + cost[i - 1], prevPrev + cost[i - 2]);
            prevPrev = prev;
            prev = cur;
        }
        return prev;
    }
}
Drill This