Dynamic Programming

Dynamic programming (DP) takes recursion's bad habit of re-solving the same small problems and fixes it: solve each subproblem *once*, save its answer in a table, and reuse it. Filling the table from the smallest cases upward turns work that would be exponential by naive recursion into a simple linear scan.

The two conditions

A problem is a DP candidate only when both of these hold:

1. 1Optimal substructure — the best answer to the whole is built from best answers to its parts. The fewest coins for 6 equals 1 + (fewest coins for 6 − c) over each coin c.
2. 2Overlapping subproblems — the same smaller problem (say dp[2]) is needed by many larger ones, so solving it once and storing it pays off. Without overlap, plain recursion is already fine.

Worked example — coin change

With coins [1, 3, 4], find the fewest coins that sum to 6. Let dp[a] be the fewest coins for amount a. Start from dp[0] = 0 and, for each amount, try every coin: dp[a] = 1 + min(dp[a − c]).

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;                       // zero coins make amount 0
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a && dp[a - c] + 1 < dp[a]) {
        dp[a] = dp[a - c] + 1;     // use coin c, then best for the rest
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Filling dp left to right for coins [1, 3, 4] gives:

amount:  0   1   2   3   4   5   6
dp:      0   1   2   1   1   2   2

dp[6] = 2 — that's 3 + 3. Each entry reused answers already sitting to its left, so no work is ever repeated.