Min Cost Climbing Stairs

Easy· 1D DP

Problem

Each step i of a staircase has a fee cost[i] that you pay when you step on it, after which you may climb 1 or 2 steps. You may start on step 0 or step 1. Return the cheapest total fee to get past the last step.

Examples

Input: cost = [10,15,20]

Output: 15

Start on step 1, pay 15, then jump 2 steps past the top.

Input: cost = [1,100,1,1,1,100,1,1,100,1]

Output: 6

Constraints

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

Hints & approach

Hint 1

The "top" is position n, one past the last index.

Hint 2

To reach position i you came from i-1 or i-2 and paid that step's cost.

Hint 3

dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) with dp[0] = dp[1] = 0.

Approachtry the hints first

Let dp[i] be the minimum fee to arrive at position i without yet paying for it. Because you can start at step 0 or 1 for free, dp[0] = dp[1] = 0. To reach i you either stood on i-1 and paid cost[i-1], or on i-2 and paid cost[i-2], so take the cheaper option. The answer is dp[n], and only the last two values need to be stored.

Time O(n) · Space O(1)

← PreviousClimbing Stairs Next →N-th Tribonacci Number