Cost array for each step. You can start at step 0 or 1. Pay cost[i] to climb from step i (then climb 1 or 2 steps). Return minimum cost to reach the top.
dp[i] = min cost to reach top from step i. You can jump 1 or 2 steps. Answer is min(dp[n-1], dp[n-2]) since you can finish from either of the last two steps.
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 −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 −1 plus cost of i −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.
Define the state precisely, here the cost to arrive at i. The top is one past the last step.
Run the animation above on your own input, or watch the 2:05 video explanation of Min Cost Climbing Stairs with a dry run and Java code.