Algorithms: Design Strategies

1. When Each item is taken whole or not, under a capacity, to make a total as large as possible

   , choose

   0/1 Knapsack

2. When You count routes across a grid that only move right or down

   , choose

   Paths Across a Grid

3. When Two sequences are compared by what they share in order, or the edits between them

   , choose

   Longest Common Subsequence

4. When One sequence, and you want the most items you can keep in increasing order

   , choose

   Longest Increasing Subsequence

5. When Every valid candidate must be listed, not only the best one or how many there are

   , choose

   Backtracking

6. When One choice at each step can be proved safe by an exchange argument

   , choose

   Greedy Algorithm

7. When The same smaller problem recurs, the answer is a best value or a count, and only some states are reached

   , choose

   Memoisation

8. When The same smaller problem recurs, the answer is a best value or a count, and every state is needed

   , choose

   Tabulation

Both build a solution one choice at a time: backtracking tries each choice and undoes it, and greedy keeps one.

• Backtracking

  Choose, explore, then undo the choice before the next; listing every subset costs O(n · 2ⁿ).

  Use when

  Every arrangement that satisfies the rules must be listed, not only the best one or a count.

  Snippet

  def explore(i):
      if i == len(items):
          found.append(list(path))
          return
      path.append(items[i])
      explore(i + 1)
      path.pop()
      explore(i + 1)

• Greedy Algorithm

  Take the choice that looks best now and never undo it; usually a sort then one scan.

  Use when

  One choice at each step can be proved safe by an exchange argument, such as earliest finish first.

  Snippet

  def most_meetings(meetings):
      count, free_from = 0, float("-inf")
      for start, end in sorted(meetings, key=lambda m: m[1]):
          if start >= free_from:
              count += 1
              free_from = end
      return count

Both store each subproblem's answer so it is solved once, and differ in the order the answers are filled.

• Memoisation

  Recurse from the whole problem and cache each state's answer; cost is states times work per state.

  Use when

  The same smaller problem recurs, and only some states are reached from the start.

  Snippet

  from functools import cache
  
  def best_total(takings):
      @cache
      def best(i):
          if i >= len(takings): return 0
          return max(best(i + 1), takings[i] + best(i + 2))
      return best(0)

• Tabulation

  Fill a table from the base cases up, with no recursion; the same cost as memoisation.

  Use when

  Every state is needed, the input is deep enough to overflow the call stack, or space must shrink.

  Snippet

  def best_total(takings):
      best = [0] * (len(takings) + 2)
      for i in range(len(takings) - 1, -1, -1):
          best[i] = max(best[i + 1], takings[i] + best[i + 2])
      return best[0]

Four dynamic programmes that recur in problems, each told apart by what indexes its table.

• 0/1 Knapsack

  Skip or take each item once, keeping the best value for every capacity: O(n × W) in every case.

  Use when

  Each item is taken whole or not at all, under a weight or budget limit, to make a total as large as possible.

  Snippet

  def knapsack(weights, values, capacity):
      best = [0] * (capacity + 1)
      for weight, value in zip(weights, values):
          for c in range(capacity, weight - 1, -1):
              best[c] = max(best[c], best[c - weight] + value)
      return best[capacity]

• Paths Across a Grid

  Each cell's count is the count from above plus the count from the left: O(rows × cols), every case.

  Use when

  You count or cost routes across a grid that move only right or down.

  Snippet

  def count_paths(rows, cols):
      ways = [1] * cols
      for _ in range(1, rows):
          for c in range(1, cols):
              ways[c] += ways[c - 1]
      return ways[-1]

• Longest Common Subsequence

  Cell (i, j) answers for the first i and j items; a match extends the diagonal: O(m × n), every case.

  Use when

  Two sequences are compared by what they share in order, or by the edits that turn one into the other.

  Snippet

  def lcs_length(a, b):
      table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
      for i, x in enumerate(a, 1):
          for j, y in enumerate(b, 1):
              table[i][j] = (table[i - 1][j - 1] + 1 if x == y
                  else max(table[i - 1][j], table[i][j - 1]))
      return table[-1][-1]

• Longest Increasing Subsequence

  Each position extends the best earlier run that ends on a smaller value: O(n²), every case.

  Use when

  One sequence, and you want the most items you can keep in increasing order.

  Snippet

  def lis_length(items):
      best = [1] * len(items)
      for i in range(len(items)):
          for j in range(i):
              if items[j] < items[i]:
                  best[i] = max(best[i], best[j] + 1)
      return max(best, default=0)

1. 01

   Forgetting to undo the choice after the recursive call, so every later branch starts from too long a path.

   Forgetting to Undo the Choice

2. 02

   Trusting a greedy rule because it works on the examples, when one counterexample breaks it.

   Trusting a Greedy Rule Without a Proof

3. 03

   Adding the value to the wrong term of the recurrence, which lets two neighbours both be taken.

   Swapping the Two Choices in the Recurrence

4. 04

   Looping upwards over capacities in a one-array knapsack, which takes the same item more than once.

   Running the One-Array Knapsack Loop Upwards

5. 05

   Sizing a sequence table m by n, which leaves no row or column for the empty prefix.

   Sizing the Table Without the Empty Prefix

6. 06

   Memoising a recursion whose subproblems never repeat, which stores every call and reuses none.

   Memoising Subproblems That Never Repeat

• Backtracking4 questions

  Practise

• Greedy Algorithms4 questions

  Practise

• Dynamic Programming6 questions

  Practise

• Knapsack and Grid Dynamic Programming4 questions

  Practise

• Sequence Dynamic Programming4 questions

  Practise