Dynamic programming is what happens when a problem keeps asking the same question twice. It breaks one hard problem into smaller ones, solves each small piece once, and stores the result so it can be reused.
That sounds neat on paper. In practice, it is a way to save time when a problem has repeated work and a clear structure.
The core idea
I find it useful to think of dynamic programming as careful reuse. If the answer to a small part of the problem will matter again later, do not solve it again from scratch.
Two traits usually make that possible. The first is overlapping subproblems, which means the same smaller problem appears many times. The second is optimal substructure, which means a good answer for the whole problem can be built from good answers to smaller parts.
If a problem does not have those traits, dynamic programming is usually the wrong tool. That is one reason it is praised too often. It is powerful, but not magical.
A small example with Fibonacci numbers
The Fibonacci sequence is the cleanest starting point. Each number is the sum of the two before it.
So if (F(6)) depends on (F(5)) and (F(4)), and those depend on earlier values, a plain recursive approach keeps asking for the same values again and again. (F(4)) gets recomputed from more than one path. That is wasted work.
Dynamic programming changes that. It saves each answer after the first time it is found. Then the next time the same value is needed, the program reads it back instead of rebuilding it.
Here is the basic shape in words:
- Find the smaller problem.
- Write down how the answer depends on smaller answers.
- Save each result once.
- Reuse the saved result when the same case appears again.
That is the whole game. The hard part is often not the code. It is seeing the smaller pieces clearly.
Top-down and bottom-up
There are two common ways to write a dynamic programming solution.
Top-down, also called memoization, starts with the full problem and breaks it apart recursively. Each time a smaller answer is found, it is stored. If the same subproblem appears later, the stored value is returned.
This version feels natural to many beginners because it looks like ordinary recursion. The risk is stack depth, and sometimes the recursive shape hides how many states are really being tracked.
Bottom-up, also called tabulation, starts with the smallest cases and builds a table step by step. It does not wait for recursion to uncover the answers. It fills the answers in a planned order.
This version can be easier to reason about once the recurrence is clear. It often uses less call overhead too. But it can feel less intuitive at first, because the code wants an ordering before the full logic feels obvious.
Both styles solve the same kind of problem. They only differ in how the saved answers are produced and reused.
What to look for in an interview problem
When a coding problem smells like dynamic programming, the first task is not writing code. It is naming the subproblems.
A useful question is this: what smaller version of the same problem do I need to solve to get the bigger answer? If that smaller version appears again and again, dynamic programming may fit.
Then comes the recurrence relation. That is just the rule that connects one answer to earlier answers. In Fibonacci, the rule is simple. In harder problems, the rule may depend on position, count, remaining capacity, or previous choices.
After that, the implementation choice appears. Memoization is often faster to sketch. Tabulation is often easier to optimize once the state is known. I see both as valid. The better one depends on what the problem makes visible.
A common interview pattern
A lot of classic problems fit this shape. Longest common subsequence is a well-known one. So are knapsack-style problems, some shortest-path questions, and many sequence problems that ask for best, count, or length under constraints.
These are not the same problem with different names. But they share a habit. Each answer depends on smaller answers, and those smaller answers get reused.
That is why people studying coding interviews often meet dynamic programming late and then struggle. The skill is not memorizing formulas. The skill is spotting repeated structure under a noisy surface.
Where it helps, and where it does not
Dynamic programming is useful when the cost of repetition is high. It trades extra memory for speed. That tradeoff can be worth it, but not always.
If a problem has no repeated subproblems, memoization adds clutter without benefit. If the states are too many, the table can grow large. If the recurrence is unclear, the method becomes guesswork, and guesswork is a bad habit in interviews.
So the honest view is simple. Dynamic programming is a tool for a narrow class of problems. It is one of the best tools in that class, but it does not belong everywhere.
The part worth remembering
For a beginner, the main win is not the code pattern. It is the way of thinking. First find the repeated subproblem. Then define the rule that links it to smaller answers. Then choose whether to store results as you go down or build them as you go up.
Once that shift clicks, dynamic programming stops looking like a pile of tricks. It becomes a clear response to a clear problem shape. That is a useful step in interview prep, because it replaces panic with structure.
The next thing to learn is a real recurrence, not another slogan. A small problem like Fibonacci or longest common subsequence is enough to show how saved answers change the whole shape of the work.
That is also where The Dravelo Field Notes fits its promise: one practical technical idea, one learning decision, and one useful network resource each edition.