You know DP has overlapping subproblems. Now comes the hard part.

Everyone wants to jump to “the formula.” But the formula is not the first step — it is a consequence of a decision you have not made yet. That decision: what does dp[i] actually mean?

Get the definition wrong, and the recurrence collapses. Get it right, and it writes itself.

Below is the Longest Increasing Subsequence problem. Your job: fill in the blanks to define what dp[i] computes.

Choose carefully — you will immediately see whether your definition produces a valid transition or an impossible one.

The comment above the code is not decoration — it IS the algorithm. Every line of the solution is a mechanical consequence of that one-line state definition.

Wrong definition? The transition breaks. Right definition? The code writes itself. This is the deepest skill in DP: choosing what to compute BEFORE choosing how to compute it.