Each step has a cost, which you pay when you stand on it. You may start on step 0 or step 1, and climb 1 or 2 steps at a time. Return the minimum cost to reach the top, which is just past the last step.
DSA Animator › DSA Revision › Dynamic Programming › Min Cost Climbing Stairs
Remember: define the state precisely, here the cost to arrive at i. The top is one past the last step. The video solves Min Cost Climbing Stairs (LeetCode 746, Easy) with the 1D DP pattern from the Dynamic Programming topic, and you can replay every step in the interactive Min Cost Climbing Stairs animation.
Each step has a cost, which you pay when you stand on it. You may start on step 0 or step 1, and climb 1 or 2 steps at a time. Return the minimum cost to reach the top, which is just past the last step.
For costs 1, 100, 1, 1, 1, 100, 1, 1, 100, 1, the answer is 6. The cheap path steps only on the ones and skips every 100.
Trying every combination of single and double steps is exponential. Many of those paths share the same suffix, which we keep recomputing.
Let dp of i be the cheapest cost to arrive at position i. Starting is free, so dp of 0 and dp of 1 are both 0. To arrive at i, you either stood on i minus 1 and paid its cost, or stood on i minus 2 and paid its cost. So dp of i is the smaller of dp of i minus 1 plus cost of i minus 1, and dp of i minus 2 plus cost of i minus 2. The top is position n, so the answer is dp of n.
dp of 0 and dp of 1 are 0. dp of 2 is 1, by standing on step 0 and paying 1. dp of 3 is 2, still avoiding the 100 on step 1. The values continue 2, 3, 3, 4, 4, 5, because each step picks the cheaper predecessor. Finally dp of 10, the top, is 6. Every 100 was skipped by a double step.
In code, create an array of size n plus 1, filled with 0. Loop i from 2 to n. Set dp of i to the minimum of the two arrivals, each plus the cost of the step it came from. Return dp of n, so it's O of n time, or O of 1 space with two variables.
Remember: define the state precisely, here the cost to arrive at i. The top is one past the last step.