What Is Dynamic Programming?

Dynamic programming is not a data structure or a trick. It is a way of organizing a problem where the answer depends on many repeated decisions. Instead of exploring the same future again and again, you define a state that represents a smaller version of the problem, solve each state once, and reuse that answer wherever it is needed.

The interview version is simple to say but hard to execute: identify what information is necessary to make the remaining choices, write the recurrence that combines smaller answers, and choose an evaluation order that guarantees dependencies are ready before they are used.

A problem is a strong DP candidate when it has choices, overlapping subproblems, and optimal substructure. Choices mean the algorithm must decide among alternatives, such as take or skip, cut here or later, match or delete, move right or down. Overlapping subproblems mean different choice paths ask for the same smaller answer. Optimal substructure means the best answer for a larger state can be built from best answers to smaller states.

Climbing Stairs has choices about the last step, repeated counts for smaller stairs, and a recurrence from n - 1 and n - 2. Coin Change has choices about which coin to use next, repeated amounts, and a minimum over smaller amounts. Edit Distance has choices among insert, delete, and replace, with states formed by prefixes of two strings.

Greedy makes one locally best choice and commits to it. It works only when a proof shows that local choices cannot block a global optimum. Dynamic programming keeps multiple competing futures alive through states, so it is safer when early decisions interact with later constraints.

Divide and conquer splits a problem into independent subproblems, solves them separately, and combines the results. Merge Sort is divide and conquer because the left and right halves do not ask for the same subarray answer repeatedly. DP is the right tool when the recursive tree recomputes the same states or when the best answer to one state is needed by many parents.

Use the same checklist for almost every DP interview problem:

1. Define the state: write exactly what dp[...] means in plain English.
2. Identify the answer state: decide which cell or variable contains the final answer.
3. Derive the transition: express one state using smaller or simpler states, usually from the last decision or next decision.
4. Set base cases and initialization: anchor the smallest states so the recurrence has somewhere to stop.
5. Choose evaluation order and space: decide top-down memoization or bottom-up tabulation, then compress memory only after the recurrence is correct.

This structure is more important than memorizing problem names. In senior interviews, clear state definition and transition derivation are what turn DP from guesswork into engineering.