Greedy and Dynamic Programming

Table of Contents

1. Two Ways to Design an Algorithm
2. Greedy: Take the Best Right Now
3. Greedy Example: Interval Scheduling
4. When Greedy Goes Wrong
5. Dynamic Programming: Remember Your Answers
6. Top-Down and Bottom-Up
7. Climbing Stairs
8. Coin Change
9. Knapsack-Lite
10. Longest Common Subsequence
11. How to Spot a DP Problem
12. Recipe: greedy.ts and dp.ts for algolab
13. Try It Yourself

1. Two Ways to Design an Algorithm

The earlier chapters taught structures and techniques you can name: hash map, stack, binary search, BFS. This chapter is about how to design an algorithm for a problem that asks for the best answer. "What is the fewest coins?" "What is the most meetings I can attend?" "What is the cheapest way?" These are optimization problems, and two strategies cover a huge share of them:

• Greedy: at each step, take the choice that looks best right now, and never look back. Fast and simple, but only correct for some problems.
• Dynamic programming (DP): break the problem into smaller overlapping problems, solve each once, and store the answers. Slower to design, but correct for a much bigger set of problems.

Where do you meet them at work? Greedy is behind scheduling meeting rooms, packing data into the fewest network packets, and giving change at a till. DP is behind spell-check "edit distance", the diff that shows what changed between two files, route planning, text wrapping, and the optimal way to split a video into chunks. Knowing both lets you look at a problem and pick the right tool.

2. Greedy: Take the Best Right Now

A greedy algorithm builds an answer one choice at a time. At every step it picks the locally best option, then commits. It never reconsiders.

A daily example: you owe someone 63 cents and have coins worth 25, 10, 5 and 1. Pay the largest coin that still fits, repeatedly:

function greedyCoins(coins: number[], amount: number): number[] {
  const sorted = [...coins].sort((a, b) => b - a); // biggest first
  const used: number[] = [];
  let left = amount;
  for (const c of sorted) {
    while (left >= c) {
      used.push(c);
      left -= c;
    }
  }
  return left === 0 ? used : [];
}

console.log(greedyCoins([25, 10, 5, 1], 63));
// [ 25, 25, 10, 1, 1, 1 ]

Six coins, and that really is the fewest for these coin values. Greedy is attractive because it is usually short and fast: sort once, then loop once. The cost is O(n log n) for the sort and O(n) for the loop.

Every greedy algorithm rests on a claim that can be proven: choosing the locally best option can never stop us from reaching the best overall answer. Sometimes the claim is true (as for these coins). Sometimes it is false. Section 4 shows what that looks like, so you do not trust greedy blindly.

3. Greedy Example: Interval Scheduling

Here is a problem where greedy is the right answer, and the choice of "best" is not obvious.

You have one meeting room and a list of meeting requests, each with a start and end time. Pick the largest number of meetings that do not overlap.

Which meeting should you take first? There are three tempting ideas:

• The one that starts earliest. Bad: a meeting from 0 to 100 would block everything.
• The shortest one. Bad: a tiny meeting in the middle can block two longer ones on each side.
• The one that ends earliest. This leaves the most room for the rest.

The third idea is the right one, and it can be proven: the meeting that ends first leaves at least as much free time as any other choice. So:

1. Sort by end time.
2. Take a meeting if it starts at or after the end of the last chosen one.

interface Interval {
  start: number;
  end: number;
}

function maxNonOverlapping(intervals: Interval[]): Interval[] {
  const sorted = [...intervals].sort((a, b) => a.end - b.end);
  const chosen: Interval[] = [];
  let lastEnd = -Infinity;

  for (const iv of sorted) {
    if (iv.start >= lastEnd) {
      chosen.push(iv);
      lastEnd = iv.end;
    }
  }
  return chosen;
}

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

console.log(maxNonOverlapping(meetings).map((m) => `${m.start}-${m.end}`));
// [ '1-4', '5-7', '8-11' ]

Walk through it. Sorted by end: 1-4, 3-5, 0-6, 5-7, 3-9, 5-9, 6-10, 8-11. Take 1-4 (last end 4). 3-5 starts at 3, before 4, so skip. 0-6 skip. 5-7 starts at 5, which is at or after 4: take it (last end 7). 3-9, 5-9 and 6-10 all start before 7: skip. 8-11 starts at 8: take. Three meetings, and no better answer exists.

The same pattern solves "minimum number of arrows to burst balloons", "minimum number of meeting rooms" (with a heap, chapter 10), and "remove the fewest intervals so the rest do not overlap". When you see intervals, think "sort by end" or "sort by start" first.

4. When Greedy Goes Wrong

Go back to coins. Suppose a strange country has coins worth 4, 3 and 1, and you must pay 6. Greedy takes the biggest first:

console.log(greedyCoins([4, 3, 1], 6));
// [ 4, 1, 1 ]   three coins

But 3 + 3 is only two coins. Greedy committed to the 4 and could not take it back. Another case: coins 5 and 2, pay 3. Greedy tries 5 (too big), tries 2, then has 1 left and no coin for it, so it returns [] (failure). Correctly, 3 cannot be paid at all with these coins. The first case is the real danger: greedy gives an answer, and the answer is wrong, with no error to warn you.

Real currencies are designed so that greedy works. Arbitrary coin sets are not. So how do you decide whether greedy is safe?

• Try to prove the "best choice never blocks the best answer" claim, or find a counterexample on a small input. Two minutes with a pencil and a tricky example saves hours of debugging.
• Greedy tends to work when a sort gives a clear order of "best", and taking it never hurts later (intervals by end time).
• Greedy tends to fail when choices interact: taking one thing changes how good the other things are (coins, packing a bag).

When greedy fails, you need to try the alternatives, and that is the doorway to dynamic programming.

5. Dynamic Programming: Remember Your Answers

You met the core idea in the recursion chapter, in a different outfit: memoization. Dynamic programming is recursion plus remembering, used when the same smaller problem comes up again and again.

Recall Fibonacci. Each number is the sum of the two before it:

function fibSlow(n: number): number {
  return n < 2 ? n : fibSlow(n - 1) + fibSlow(n - 2);
}

It is correct and short, and it is slow. fib(5) calls fib(4) and fib(3). But fib(4) also calls fib(3). The same work is repeated:

                fib(5)
              /        \
          fib(4)       fib(3)        <- fib(3) is computed twice
         /     \       /    \
     fib(3)  fib(2) fib(2) fib(1)    <- fib(2) three times in total

The number of calls roughly multiplies by 1.6 each time n goes up by one. Counting real calls:

That is O(2^n) growth. You saw the shape of this curve in the Big-O chapter. fib(35) already takes tens of milliseconds, and fib(50) would take over a minute.

Two ingredients tell you DP is possible:

1. Overlapping subproblems: the same smaller problem is needed many times (fib(3) above). If every subproblem were different, there would be nothing to reuse. That is plain divide and conquer, like merge sort.
2. Optimal substructure: the best answer to the big problem is built from the best answers to the smaller ones.

6. Top-Down and Bottom-Up

There are two ways to write a DP solution. Both do the same work, with the same Big-O.

Top-down (memoization): write the plain recursion, then add a cache. Before computing, check if it is already there:

function fibMemo(n: number, memo = new Map<number, number>()): number {
  if (n < 2) return n;
  const cached = memo.get(n);
  if (cached !== undefined) return cached;

  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

console.log(fibMemo(10)); // 55
console.log(fibMemo(50)); // 12586269025

Each value of n is computed once, so the cost drops from O(2^n) to O(n) time and O(n) space (the cache, plus the recursion stack).

Bottom-up (tabulation): skip recursion. Fill a table from the smallest subproblem upward, so everything you need is already there:

function fibTable(n: number): number {
  if (n < 2) return n;
  let prev = 0;
  let curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

console.log(fibTable(50)); // 12586269025

Because each value only needs the previous two, we do not even keep a full table, just two variables. That makes the space O(1). Squeezing a table down to the few cells you still need is a common DP finishing touch.

A note on numbers: fib(78) is the last Fibonacci number a JavaScript number holds exactly. Past that, results quietly lose precision (the integer limit from the Math series). Use BigInt if you need fib(100).

A practical recipe for any DP problem, whichever style you pick:

1. Define the state: what do the inputs of the subproblem mean? ("dp[i] is the fewest coins to make amount i.")
2. Write the recurrence: how does a state depend on smaller states?
3. Set the base cases: the smallest states you know directly.
4. Decide the order: which states must be ready before others.
5. Read the answer: which state is the final answer?

7. Climbing Stairs

A famous first DP problem. You climb a staircase with n steps. Each move, you take 1 or 2 steps. How many different ways can you reach the top?

Follow the recipe. Let ways(n) be the number of ways to reach step n. You arrived at step n either from step n - 1 (with a 1-step move) or from step n - 2 (with a 2-step move). These two groups of paths do not overlap, so:

ways(n) = ways(n - 1) + ways(n - 2)

With base cases ways(0) = 1 (stand still: one way) and ways(1) = 1. It is the Fibonacci recurrence in disguise.

function climbStairs(n: number): number {
  let a = 1; // ways(0)
  let b = 1; // ways(1)
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

console.log([1, 2, 3, 4, 5, 10].map(climbStairs));
// [ 1, 2, 3, 5, 8, 89 ]

Check n = 3 by hand: 1+1+1, 1+2, 2+1. That is 3 ways. For n = 4: 1111, 112, 121, 211, 22. That is 5.

This is a useful lesson. Many different-looking problems are the same recurrence in a costume. "How many ways to tile a 2 x n strip with dominoes" and "binary strings of length n with no two 1s in a row" have the same Fibonacci shape. Another one-line variation is "House Robber": you cannot rob two neighboring houses, so for each house the best total is either the best without it, or this house plus the best that skips the previous one:

function houseRobber(nums: number[]): number {
  let take = 0; // best total if we rob the current house
  let skip = 0; // best total if we do not
  for (const n of nums) {
    [take, skip] = [skip + n, Math.max(take, skip)];
  }
  return Math.max(take, skip);
}

console.log(houseRobber([2, 7, 9, 3, 1])); // 12   (2 + 9 + 1)
console.log(houseRobber([1, 2, 3, 1]));    // 4    (1 + 3)

8. Coin Change

Now the problem where greedy failed. Given coin values and an amount, find the fewest coins that add up to the amount, or -1 if it is impossible.

State: dp[a] is the fewest coins to make amount a. Base: dp[0] = 0. Recurrence: to make a, the last coin could be any coin c. Then you need the best answer for a - c, plus this one coin. Try every coin and keep the smallest:

dp[a] = 1 + min(dp[a - c])  for every coin c with c <= a

function coinChange(coins: number[], amount: number): number {
  const dp = new Array<number>(amount + 1).fill(Infinity);
  dp[0] = 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;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([4, 3, 1], 6));   // 2   (3 + 3)
console.log(coinChange([5, 2], 3));      // -1
console.log(coinChange([1, 2, 5], 11));  // 3   (5 + 5 + 1)
console.log(coinChange([2], 3));         // -1
console.log(coinChange([1], 0));         // 0

Using Infinity as "not reachable yet" is a neat trick: Infinity + 1 is still Infinity, so impossible states never beat a real answer.

Here is the table filled in for coins [4, 3, 1] and amount 6:

Read dp[6]: try coin 4, which leaves dp[2] = 2, so 3 coins. Try coin 3: dp[3] = 1, so 2 coins. Try coin 1: dp[5] = 2, so 3 coins. The best is 2. Greedy missed this because it never compared alternatives.

The time cost is O(amount × number of coins), and the space is O(amount). That is fast even for a large amount, whereas trying every combination is exponential.

9. Knapsack-Lite

You have a bag that holds a total weight of capacity. Each item has a weight and a value, and you can take each item at most once. Pick items for the maximum total value. This is the 0/1 knapsack, the model for budgeting, cargo loading, and choosing which features fit into a sprint.

Greedy by "best value per weight" can fail here, just as it did for coins. Take items (weight 10, value 60), (weight 20, value 100) and (weight 30, value 120) with capacity 50. The ratios are 6, 5 and 4, so greedy takes the first two (value 160) and the third no longer fits. But the second and third together weigh exactly 50 and are worth 220.

State: dp[w] is the best value using at most weight w. Process items one at a time. For each item, update the table from the heaviest capacity down to the item's weight, so that the item is used at most once:

function knapsack(
  items: { weight: number; value: number }[],
  capacity: number,
): number {
  const dp = new Array<number>(capacity + 1).fill(0);

  for (const { weight, value } of items) {
    for (let w = capacity; w >= weight; w--) {
      dp[w] = Math.max(dp[w], dp[w - weight] + value);
    }
  }
  return dp[capacity];
}

console.log(
  knapsack(
    [
      { weight: 1, value: 15 },
      { weight: 3, value: 20 },
      { weight: 4, value: 30 },
    ],
    4,
  ),
); // 35

console.log(
  knapsack(
    [
      { weight: 10, value: 60 },
      { weight: 20, value: 100 },
      { weight: 30, value: 120 },
    ],
    50,
  ),
); // 220

In the first call, the best is the first two items (weight 1 + 3 = 4, value 15 + 20 = 35). The inner loop goes downward on purpose. If it went upward, dp[w - weight] might already include the current item, and you would use it twice. That turns the problem into the "unlimited items" version. This single loop direction is a classic interview trap.

Time is O(items × capacity), space O(capacity). Be careful with the name: this is called pseudo-polynomial, because it grows with the value of capacity, not with how many digits it has.

10. Longest Common Subsequence

Given two strings, find the length of their longest common subsequence (LCS): the longest sequence of characters that appears in both, in the same order, but not necessarily next to each other. For "abcde" and "ace", the answer is 3 ("ace"). This is the heart of the diff tool and DNA comparison.

This one has two changing inputs, so the state is a table with two dimensions: dp[i][j] is the LCS length of the first i characters of a and the first j characters of b.

• If the characters a[i-1] and b[j-1] match, they extend the best answer for the shorter prefixes: dp[i][j] = dp[i-1][j-1] + 1.
• If they do not match, drop one character from either side and take the better result: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
• Base: with an empty string, the answer is 0, so row 0 and column 0 are zeros.

function lcs(a: string, b: string): number {
  const dp: number[][] = Array.from({ length: a.length + 1 }, () =>
    new Array<number>(b.length + 1).fill(0),
  );

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      dp[i][j] =
        a[i - 1] === b[j - 1]
          ? dp[i - 1][j - 1] + 1
          : Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[a.length][b.length];
}

console.log(lcs("abcde", "ace"));         // 3
console.log(lcs("abc", "def"));           // 0
console.log(lcs("AGGTAB", "GXTXAYB"));    // 4   ("GTAB")

The table is (m + 1) × (n + 1), so both time and space are O(m × n). The common mistake is mixing up the dimension: note the rows use a.length + 1 and the columns b.length + 1. Another is the off-by-one: the table index i refers to the character at a[i - 1]. If only the length is needed, you can keep two rows instead of the whole table to reduce space to O(n). Edit distance (how many insertions, deletions and swaps turn one word into another) has the same two-dimensional shape.

11. How to Spot a DP Problem

DP problems rarely say "use DP". Look for these signals:

A reliable approach for an interview:

1. Write the brute-force recursion first, even if slow. Say what the inputs of the function mean. These are your state.
2. Notice the repeated calls. That proves there are overlapping subproblems.
3. Add a memo (top-down). You are now done, with correct code.
4. If asked, convert it to a table (bottom-up) and then shrink the space.

Doing it in this order means you always have a correct answer in hand, and every later step is an optimization.

And how to choose between greedy and DP? Try greedy first on a tiny example and look for a counterexample. If you cannot break it, and the reason is clear (a sort gives a natural order), greedy is right. If you find a counterexample, or the choices interact, go to DP.

12. Recipe: greedy.ts and dp.ts for algolab

Create src/greedy.ts:

export interface Interval {
  start: number;
  end: number;
}

// Largest set of non-overlapping intervals (sort by end time).
export function maxNonOverlapping(intervals: Interval[]): Interval[] {
  const sorted = [...intervals].sort((a, b) => a.end - b.end);
  const chosen: Interval[] = [];
  let lastEnd = -Infinity;

  for (const iv of sorted) {
    if (iv.start >= lastEnd) {
      chosen.push(iv);
      lastEnd = iv.end;
    }
  }
  return chosen;
}

// Largest-coin-first change. Only correct for "nice" coin systems.
export function greedyCoins(coins: number[], amount: number): number[] {
  const sorted = [...coins].sort((a, b) => b - a);
  const used: number[] = [];
  let left = amount;

  for (const c of sorted) {
    while (left >= c) {
      used.push(c);
      left -= c;
    }
  }
  return left === 0 ? used : [];
}

Create src/dp.ts:

export function fibMemo(
  n: number,
  memo = new Map<number, number>(),
): number {
  if (n < 2) return n;
  const cached = memo.get(n);
  if (cached !== undefined) return cached;

  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

export function climbStairs(n: number): number {
  let a = 1;
  let b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

export function houseRobber(nums: number[]): number {
  let take = 0;
  let skip = 0;
  for (const n of nums) {
    [take, skip] = [skip + n, Math.max(take, skip)];
  }
  return Math.max(take, skip);
}

// Fewest coins to make `amount`, or -1 if impossible.
export function coinChange(coins: number[], amount: number): number {
  const dp = new Array<number>(amount + 1).fill(Infinity);
  dp[0] = 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;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// 0/1 knapsack: best total value within the capacity.
export function knapsack(
  items: { weight: number; value: number }[],
  capacity: number,
): number {
  const dp = new Array<number>(capacity + 1).fill(0);
  for (const { weight, value } of items) {
    for (let w = capacity; w >= weight; w--) {
      dp[w] = Math.max(dp[w], dp[w - weight] + value);
    }
  }
  return dp[capacity];
}

// Length of the longest common subsequence of two strings.
export function lcs(a: string, b: string): number {
  const dp: number[][] = Array.from({ length: a.length + 1 }, () =>
    new Array<number>(b.length + 1).fill(0),
  );
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      dp[i][j] =
        a[i - 1] === b[j - 1]
          ? dp[i - 1][j - 1] + 1
          : Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[a.length][b.length];
}

Create src/dp.test.ts:

import { test } from "node:test";
import assert from "node:assert/strict";
import { maxNonOverlapping, greedyCoins } from "./greedy.ts";
import {
  fibMemo,
  climbStairs,
  houseRobber,
  coinChange,
  knapsack,
  lcs,
} from "./dp.ts";

test("interval scheduling picks the most meetings", () => {
  const picked = maxNonOverlapping([
    { start: 1, end: 4 },
    { start: 3, end: 5 },
    { start: 0, end: 6 },
    { start: 5, end: 7 },
    { start: 8, end: 11 },
  ]);
  assert.equal(picked.length, 3);
});

test("greedy coins works for nice systems, fails for odd ones", () => {
  assert.deepEqual(greedyCoins([25, 10, 5, 1], 63), [25, 25, 10, 1, 1, 1]);
  assert.equal(greedyCoins([4, 3, 1], 6).length, 3); // not optimal
  assert.equal(coinChange([4, 3, 1], 6), 2); // DP finds 3 + 3
});

test("fibonacci and stairs", () => {
  assert.equal(fibMemo(10), 55);
  assert.equal(fibMemo(50), 12586269025);
  assert.equal(climbStairs(5), 8);
  assert.equal(climbStairs(10), 89);
});

test("house robber", () => {
  assert.equal(houseRobber([2, 7, 9, 3, 1]), 12);
  assert.equal(houseRobber([1, 2, 3, 1]), 4);
});

test("coinChange", () => {
  assert.equal(coinChange([1, 2, 5], 11), 3);
  assert.equal(coinChange([5, 2], 3), -1);
  assert.equal(coinChange([1], 0), 0);
});

test("knapsack", () => {
  const items = [
    { weight: 1, value: 15 },
    { weight: 3, value: 20 },
    { weight: 4, value: 30 },
  ];
  assert.equal(knapsack(items, 4), 35);
});

test("lcs", () => {
  assert.equal(lcs("abcde", "ace"), 3);
  assert.equal(lcs("AGGTAB", "GXTXAYB"), 4);
  assert.equal(lcs("abc", "def"), 0);
});

Run the tests:

npx tsx --test

To feel why memoization matters, time the slow version against the cached one. Create bench-fib.ts in the algolab folder:

import { fibMemo } from "./src/dp.ts";

function fibSlow(n: number): number {
  return n < 2 ? n : fibSlow(n - 1) + fibSlow(n - 2);
}

console.time("fibSlow(35)");
console.log(fibSlow(35));
console.timeEnd("fibSlow(35)");

console.time("fibMemo(35)");
console.log(fibMemo(35));
console.timeEnd("fibMemo(35)");

npx tsx bench-fib.ts

Both lines print 9227465. The slow one takes tens of milliseconds (your machine will differ) and the memoized one is effectively instant. Now change 35 to 45 for the slow version and notice how quickly the time grows, while the memoized one still finishes at once.

13. Try It Yourself

1. Break greedy. Find coin values (other than [4, 3, 1]) where greedy gives a wrong answer for some amount. Prove it using greedyCoins and coinChange side by side. Then check that US coins [25, 10, 5, 1] never disagree for amounts 0 to 200.
2. Minimum number of rooms. Given meeting intervals, find the fewest rooms needed so no two meetings in the same room overlap. Hint: sort by start and keep a min-heap of end times (chapter 10). (Interview classic.)
3. Ways to make change. Change coinChange to count how many different combinations of coins make the amount (order does not matter). Hint: put the coin loop on the outside, and add instead of taking a minimum. For [1, 2, 5] and 5, the answer is 4.
4. Minimum path sum. In a grid of non-negative numbers, move only right or down from the top-left to the bottom-right, minimizing the sum of cells visited. Define the state dp[r][c] and write the recurrence. (Interview-style.)
5. Longest increasing subsequence. For [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4 (2, 3, 7, 18). Use dp[i] as the longest increasing subsequence ending at index i. It is O(n^2); look up the O(n log n) version with binary search (chapter 7) afterward.
6. Edit distance. Write editDistance(a, b) that returns the fewest insertions, deletions and replacements to turn a into b. For "kitten" and "sitting" the answer is 3. It has the same table shape as lcs.

Greedy takes the best-looking choice and never looks back. Dynamic programming solves each smaller problem once and remembers the answer. Between them you can attack most "best way to" questions. In the final chapter, Putting It Together, we collect every structure and technique from the series into a pattern cheat sheet, practice a step-by-step method for interview problems, and wire all the algolab modules into one package.