Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 746 Min Cost Climbing Stairs - State Definition

What dp[i] means

I'll define dp[i] as the minimum cost to reach step i without yet paying cost[i]. Your state must contain all information needed to solve the subproblem.

Base cases: dp[0] = 0 and dp[1] = 0 because you can start on step 00 or step 11 for free. You only pay a step's cost when you leave it. For i >= 2, you arrive from i-1 (paying cost[i-1]) or i-2 (paying cost[i-2]). Take the minimum: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]).

The final answer is dp[n], the cost to reach position n (one past the last step).