Introduction to Dynamic Programming

Why this lesson matters

Dynamic Programming, or DP, is one of the biggest jumps many engineers make when moving from everyday application logic to advanced algorithmic problem solving.

As a full stack engineer, you already think in terms of decomposition: routes, components, services, queues, caches, and infrastructure layers. DP uses a similar instinct, but applies it to optimization problems where the same smaller decisions keep showing up.

In this first lesson, we will set the mental model:

• What Dynamic Programming is
• What kinds of problems it solves
• Why repeated subproblems matter
• How storing earlier answers changes performance

Later lessons will go deeper into recursion, memoization, top-down DP, bottom-up DP, and optimization techniques.

Dynamic Programming in one sentence

Dynamic Programming solves a large problem by solving smaller, reusable subproblems and combining their answers.

The key word is reusable.

If every smaller problem is unique, storing answers does not help much. But if the same subproblem appears again and again, DP can avoid doing the same work repeatedly.

A rough mental model:

Big problem
├── subproblem A
│   ├── subproblem C
│   └── subproblem D
├── subproblem B
│   ├── subproblem C   <- same work appears again
│   └── subproblem E

DP says: once we solve subproblem C, keep the answer. Next time, reuse it.

When should DP come to mind?

Dynamic Programming is especially useful when a problem has two properties.

1. Overlapping subproblems

The same smaller problems appear multiple times.

Example: calculating a value for n = 5 may require values for n = 4 and n = 3; calculating n = 4 may also require n = 3. That repeated n = 3 work is a clue.

2. Optimal substructure

The best answer to the big problem can be built from best answers to smaller problems.

For example, the cheapest path across a network can often be described as:

cheapest way to get here + cost of the next hop

You do not need to memorize formal definitions yet. For now, train your eye to ask:

• Am I recomputing the same smaller thing?
• Can a larger answer be assembled from smaller answers?

Which situation is the strongest clue that Dynamic Programming may help?

Seeing repeated subproblems

Here is a small JavaScript example that intentionally does repeated work.

Do not focus on mastering recursion yet; that comes next. For now, notice how often the same input value is requested.

The function below computes Fibonacci numbers in a straightforward way, then counts how many times each n was evaluated.

```javascript
const calls = new Map();

function fib(n) {
  calls.set(n, (calls.get(n) || 0) + 1);

  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

const result = fib(6);

console.log('fib(6) =', result);
console.log('Call counts:');

for (const [n, count] of [...calls.entries()].sort((a, b) => a[0] - b[0])) {
  console.log(`n=${n}: called ${count} time(s)`);
}
```

True or false: Dynamic Programming is mainly about finding repeated subproblems and reusing their answers instead of recomputing them.

Storing answers explicitly

A common DP move is to create a place where solved subproblems live.

Imagine a service can scale from 0 to n replicas. Each operation can add either 1 or 2 replicas. How many distinct scaling sequences reach exactly n replicas?

For n = 4, examples include:

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2

The number of ways to reach i replicas depends on already-solved smaller values:

ways[i] = ways[i - 1] + ways[i - 2]

This is a first glimpse of the DP style: define smaller states, store their answers, and build toward the target.

```javascript
function countScalingSequences(targetReplicas) {
  const ways = Array(targetReplicas + 1).fill(0);

  ways[0] = 1; // one way to do nothing
  ways[1] = 1; // one operation: +1

  for (let i = 2; i <= targetReplicas; i++) {
    ways[i] = ways[i - 1] + ways[i - 2];
  }

  console.log('DP table:', ways);
  return ways[targetReplicas];
}

console.log('Ways to reach 4 replicas:', countScalingSequences(4));
console.log('Ways to reach 6 replicas:', countScalingSequences(6));
```

A problem has ____ when the same smaller problems appear again and again inside the larger problem.

A practical checklist

When approaching a DP problem, use this lightweight workflow.

1. Define the state

What smaller question are you answering?

Example: ways[i] means the number of ways to reach exactly i replicas.

2. Define the transition

How does one state depend on earlier states?

Example: ways[i] = ways[i - 1] + ways[i - 2].

3. Define base cases

What answers are known without further work?

Example: ways[0] = 1, ways[1] = 1.

4. Decide how answers are stored

This could be a table, array, map, or another structure.

We will revisit these ideas in more detail when we compare recursive, memoized, top-down, and bottom-up approaches.

What DP is not

Dynamic Programming can feel mysterious because people often describe it as a bag of tricks. It is better to think of it as a disciplined way to avoid repeated work.

DP is not just recursion

Many DP solutions start with recursive thinking, but DP is about reusable subproblem results. Recursion is one possible path to get there.

DP is not always faster by magic

Storing answers uses memory. The tradeoff is usually: spend extra space to save a lot of repeated computation.

DP is not only for math puzzles

You can see DP-like thinking in scheduling, routing, cost optimization, inventory planning, infrastructure capacity planning, and UI state flows.

The algorithmic version is more formal, but the engineering instinct is familiar: cache useful intermediate results when repeated work becomes expensive.

Which definition best describes Dynamic Programming?