Coding

Dynamic programming

Optimal substructure + overlapping subproblems → memoize/tabulate.

Coding pattern

Overview

Dynamic programming solves problems with overlapping subproblems by defining a state, a recurrence between states, and base cases — then filling a table so each subproblem is computed once. The hard part is naming the right state.

How it works

Coding pattern

ClientServiceDataEdge

Step by step, with examples

1
State
- Define dp[i]'s meaning and the base case.
2
Recurrence
- Express dp[i] from smaller states.
3
Table / memo
- Iterate bottom-up or memoize top-down.
4
Answer
- Read the final cell.
- Example: Coin change, LIS

When to reach for it

Min/max paths
Counting ways
Decision over items

Example problem

Coin Change — fewest coins to make an amount.

Approach

dp[x] = min coins to make x
For each coin, dp[x] = min(dp[x], dp[x−coin]+1)

Solution

function coinChange(coins, amount) {
  const dp = Array(amount+1).fill(Infinity);
  dp[0] = 0;
  for (let x = 1; x <= amount; x++)
    for (const c of coins)
      if (c <= x) dp[x] = Math.min(dp[x], dp[x-c] + 1);
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Complexity

Time O(amount·coins), Space O(amount).

Common pitfalls

Wrong base case
Iterating coins/amount in the wrong order

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions