What dynamic programming actually is

Dynamic programming is not a special algorithm. It is recursion that refuses to compute the same thing twice.

A problem qualifies when it has both:

1. Overlapping subproblems — the same subproblem appears many times.
2. Optimal substructure — an optimal answer is built from optimal answers to subproblems.

Missing the first, plain recursion or divide and conquer is enough (merge sort's halves never repeat). Missing the second, DP does not apply at all.

Seeing the overlap

const fib = (n) => (n < 2 ? n : fib(n - 1) + fib(n - 2));

fib(5) calls fib(3) twice, fib(2) three times, fib(1) five times. The tree has about 2ⁿ nodes but only n distinct subproblems. Everything else is repetition.

const fib = (n, memo = new Map()) => {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);

  memo.set(n, fib(n - 1, memo) + fib(n - 2, memo));
  return memo.get(n);
};

O(2ⁿ) becomes O(n), from two lines. That is the entire idea; the rest is bookkeeping.

The complexity formula

Cost = number of distinct states × work per state.

For Fibonacci: n states, O(1) work each, O(n). For the 0/1 knapsack: n × capacity states, O(1) work each, O(n × capacity). Learn to compute this before writing code — it tells you immediately whether the approach is viable.

Where the difficulty actually lies

Not in memoising. In defining the state: what parameters uniquely identify a subproblem?

• Fibonacci: n.
• Knapsack: (index, remaining capacity).
• Edit distance: (i, j) — positions in the two strings.
• Longest increasing subsequence: (index), meaning "best subsequence ending here".

Choose too few parameters and different situations collide; too many and the table explodes. Everything else follows once the state is right.

The give-away signals

A problem is probably DP if it asks for the number of ways, the minimum or maximum over choices, or whether something is achievable — and each step offers a small set of choices whose consequences overlap. Those phrasings cover most of the DP questions you will ever be asked.