Dynamic Programming • 1D Arrays

Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Pay the cost to climb one or two steps to reach the top.

Overview

This is a direct variation of the classic Fibonacci sequence or "Climbing Stairs" problem, but instead of counting ways, we are minimizing cost.

`dp[i]` represents the minimum cost to REACH step `i`. Notice it's the cost to reach it, not the cost to leave it.

To reach step `i`, you either came from step `i-1` (and paid `cost[i-1]`) or you came from step `i-2` (and paid `cost[i-2]`). Take the minimum.

Since `dp[i]` only depends on `dp[i-1]` and `dp[i-2]`, we only need two variables to track the state, reducing space complexity to O(1).

Cost: 10

Step 0

Cost: 15

Step 1

Cost: 20

Step 2

TOP

End

DP Array (Min Cost to Reach Step)

0

Code Tracker

:::

1let dp = new Array(n + 1).fill(0);

2// We can start at step 0 or 1 with cost 0

3dp[0] = 0;

4dp[1] = 0;

5for (let i = 2; i <= n; i++) {

6 dp[i] = Math.min(

7 dp[i-1] + cost[i-1], // 1 step jump

8 dp[i-2] + cost[i-2] // 2 step jump

9 );

10}

11return dp[n];