What is the difference between DP and a greedy algorithm?

AlgorithmsJunior~3 min read

What is the difference between DP and a greedy algorithm?

Short answer

DP (dynamic programming) systematically explores the state space and reuses the results of subproblems. It gives a guaranteed optimal solution when optimal substructure is present; it's usually more expensive in time/memory, but more universal.
A greedy algorithm makes the locally best choice at each step without backtracking. It's fast and simple, but requires the greedy-choice property; without it, it may give a suboptimal result.

Dynamic programming (DP): we split the problem into subproblems, solve each one once, store the result, and combine the answers. The basis is optimal substructure (the optimum is built from the optima of subproblems) and overlapping subproblems.

Greedy algorithm: at each step we choose the locally best option by some criterion, without going back. Correctness is possible when the greedy-choice property holds: a local choice can be "exchanged" for part of the optimal solution without losing quality.

Key differences

Optimality guarantee: DP - yes (with a correct model); greedy - only if the greedy-choice property is proven.
Strategy: DP builds and reuses a table/cache of states (bottom-up/memoization); greedy makes a sequence of local decisions without a cache or backtracking.
Memory: DP stores tables of states (often O(number of states)); greedy is almost always O(1)-O(n).
Time: DP is usually polynomial in the size of the state space; greedy is often O(n log n) or O(n).
Correctness proof: DP is proven through the recurrence and induction/Bellman's principle; greedy is proven through an exchange argument or a proof of the greedy-choice property.
Flexibility: DP applies more broadly; greedy is much simpler and faster wherever it applies.

How to decide which to use

Signs of DP: subproblems repeat; the solution is described through a small "state"; it's easy to write the recurrence; you need a precise guarantee of the optimum.
Signs of greedy: a natural local criterion can be formulated (sorting by it plus a single-pass selection); an exchange argument can be built; no counterexample is found.

Example 1: coin change (minimum coins)

Coins {1, 3, 4}, amount 6. Greedy takes 4 -> remainder 2 -> 1+1 = 3 coins, which is not optimal. The optimum is 3+3 = 2 coins. DP always finds the optimum (for this formulation).

// Greedy coin change (can give a non-optimal result)
function coinChangeGreedy(coins, amount) {
  coins = [...coins].sort((a, b) => b - a);
  let count = 0;
  for (const c of coins) {
    const use = Math.floor(amount / c);
    count += use;
    amount -= use * c;
  }
  return amount === 0 ? count : Infinity;
}

console.log(coinChangeGreedy([1, 3, 4], 6)); // 3 (4 + 1 + 1) - not optimal; the optimum is 2 (3 + 3)

// DP: minimum coins (tabulation)
function coinChangeDP(coins, amount) {
  const INF = 1e9;
  const dp = new Array(amount + 1).fill(INF);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (a - c >= 0) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    }
  }
  return dp[amount] === INF ? -1 : dp[amount];
}

console.log(coinChangeDP([1, 3, 4], 6)); // 2 (3 + 3)

Example 2: selecting non-overlapping intervals (greedy works)

Classic problem: select the maximum number of non-overlapping intervals. The greedy criterion: sort by end time and take each next non-overlapping interval. Proven through an exchange argument.

function selectMaxActivities(intervals) {
  intervals.sort((a, b) => a.end - b.end);
  const result = [];
  let lastEnd = -Infinity;
  for (const it of intervals) {
    if (it.start >= lastEnd) {
      result.push(it);
      lastEnd = it.end;
    }
  }
  return result;
}

const intervals = [
  { start: 1, end: 4 },
  { start: 3, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 8, end: 9 },
];

console.log(selectMaxActivities(intervals)); // greedy gives the optimum

Interview cheat sheet

Formulate the optimality criterion and the state (which parameters describe the subproblem).
Check optimal substructure and overlapping subproblems -> if yes, confidently propose DP (top-down with memoization or bottom-up).
Try a greedy criterion: sort, propose a local choice, find/refute a counterexample. If there are no counterexamples and there is an exchange argument, choose greedy.
Estimate the time and memory complexity; state why the method guarantees optimality (or when it might fail).

Summary of differences

Criterion	DP	Greedy
Idea	Explore states while reusing results	Locally best choice without backtracking
Correctness conditions	Optimal substructure, overlapping subproblems	Greedy-choice property (exchange argument)
Solution optimality	Guaranteed (with a correct model)	Not guaranteed without proving the property
Memory	Higher (state tables)	Lower (often O(1)-O(n))
Typical complexity	O(number of states × number of transitions)	O(n log n) or O(n)
Example	Minimum coins, knapsack, LIS	Interval selection, Huffman, minimum-cost problems under canonical systems

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.

What is the difference between DP and a greedy algorithm?