Dynamic programming is the part of problem solving that deals with repeated work. It shows up when a recursive idea keeps solving the same smaller problem again and again. In plain terms, it is a way to save answers and reuse them.
That sounds simple. The useful part is more specific. Dynamic programming, or DP, fits problems where smaller subproblems overlap and the whole problem can be built from those smaller answers.
What makes a problem fit
A DP problem usually has two traits.
First, the problem can be split into smaller parts. Second, those smaller parts are not all different. The same subproblem appears many times.
That is the trap in plain recursion. A recursive function may look neat, but it can repeat the same calculation at every branch. DP cuts out that waste by keeping the result of each subproblem in a table or array.
There is another trait as well. The final answer must depend on the answers to the smaller pieces. If the whole problem cannot be built from smaller solved parts, DP is not a natural fit.
This is why DP feels less like a trick and more like record keeping. It does not invent a new answer. It remembers old ones.
The basic idea in small steps
The idea is usually built in one of two ways.
One way is top-down with memoization. Start with the big problem. When a recursive call asks for a smaller answer, store that answer the first time it is found. If the same subproblem comes back later, return the saved result.
The other way is bottom-up with iteration. Start from the smallest subproblems. Fill a table in an order that makes each new entry depend only on entries already filled in.
Both versions do the same job. They avoid repeated work. The choice is mostly about style, clarity, and how easy the state is to define.
A state is the piece of information that identifies one subproblem. In DP, the state must be small enough to store and specific enough to tell one subproblem from another.
A small example with Fibonacci numbers
Fibonacci numbers are a classic example because they expose the waste clearly.
The rule is simple. Each number is the sum of the two before it. So to find the 6th number, a recursive method asks for the 5th and 4th. But the 5th asks for the 4th and 3rd. The 4th gets asked again. The 3rd gets asked again too.
That repeated work grows fast.
With DP, the earlier results are kept. If the 4th Fibonacci number is already known, it is not computed again. If the 3rd is already known, it is reused at once.
A bottom-up version makes this even clearer. Start with the first two values. Then fill in the next one, then the next. Each new number depends on the two already stored. No branch repeats the same effort.
This example is small, but the lesson is real. DP is not about Fibonacci itself. It is about seeing repeated structure and refusing to pay for it twice.
What the method changes
DP changes the shape of the solution.
Without DP, a recursive tree can branch into many repeated paths. With DP, each distinct state is solved once. That can turn a slow solution into a much faster one.
It also changes how the problem is described. Instead of asking, “How do I solve the whole thing at once?” DP asks, “What smaller answers do I need, and how do I store them?” That shift is often the real work.
There is a tradeoff. DP usually uses more memory than plain recursion because it stores answers. That is the cost of saving time. The method is useful when that cost is worth it.
Common signs that DP may apply
A few patterns show up again and again.
- The problem can be broken into smaller subproblems.
- The same subproblems appear more than once.
- The final answer can be built from smaller answers.
- The order of solving the subproblems can be arranged so earlier results help later ones.
When those signs are present, DP is worth testing as a design. Not every such problem needs it, but the fit is often strong.
Several well-known problems use this pattern. Matrix chain multiplication asks how to parenthesize a product with the least cost. The 0/1 knapsack problem tracks which item choices fit a capacity limit. Longest common subsequence compares two strings by reusing answers for prefixes. Floyd-Warshall style path methods fill a table of shortest routes step by step. These are different tasks, but the same habit appears in all of them.
What the table really means
The table is not the point. It is the memory.
Each entry stands for one solved subproblem. The meaning of the table must be clear before the code starts. If the state is vague, the table becomes a pile of numbers with no logic behind it.
A good DP table answers three questions.
What does one cell mean? What smaller cells does it depend on? In what order can the cells be filled?
If those three answers are clean, the rest is usually manageable. If they are not, the problem often feels harder than it should.
That is why DP can seem mysterious at first. The hard part is often not the loop. The hard part is naming the state.
A practical way to think about it
I read DP as a disciplined refusal to repeat work. That is all it is at heart.
The method starts with a recursive or iterative structure, then asks where the repeated effort lives. Once that repetition is visible, the solution can be stored and reused. The result is a cleaner and usually faster program.
The limits matter too. DP is not a magic speed button. It helps when overlapping subproblems are real and the state space is manageable. If the state explodes, the table can become too large to be practical.
So the lesson is narrow, but useful. Dynamic programming is the tool for problems that can be split into shared smaller parts and rebuilt from saved answers.
The next time a problem keeps asking the same question, the DP lens gives a clear answer. It shows how the subproblems fit, how the table is named, and why the repeated work can stop. That is the kind of practical idea The Dravelo Field Notes is built around: one technical point, one learning decision, and one useful network resource in a form that stays usable.