pattern heroPT–23LeetCode Extension

Dynamic programming (DP)

Break the problem into small subproblems and keep each answer in a table. Brute force solves the same subproblems again and again; this way each one is solved once.

Variant
P21 Dynamic programming (DP)1D array · 1×

Example problem: the most money from houses [3, 7, 3, 2, 6, 8, 6, 1] when you cannot rob two neighbours.

housesbest0317233246586671
this stepfilledread fromnot robbedanswer

An empty table, one cell per house

best = [–, –, –, –, –, –, –, –]i = –skip = –take = –
01/28
restart · back · play · step
Speed
1function rob(money):
2 best = new array of size len(money)
3 best[0] = money[0]
4 best[1] = max(money[0], money[1])
5 for i from 2 to len(money) - 1:
6 skip = best[i - 1]
7 take = best[i - 2] + money[i]
8 best[i] = max(skip, take)
9 return best[len(money) - 1]

← → step · space play/pause

How to recognise

the most, the least or the number of ways, where each choice limits the next ones and the same smaller question comes up again and again.

How to solve problems like this

  1. Say what one cell means: best[i] is the answer for the first i + 1 items.
  2. Write how a cell follows from earlier cells by looking at the last choice.
  3. Fill the base cases, then the cells in an order where everything a cell reads is ready.
  4. Take the answer from the last cell. To save memory, keep only the cells you still read.

Variant: 2D table

The same, but the table is two-dimensional: a cell depends on neighbouring cells filled earlier, such as the ones above and to the left. It fits paths on a grid.

  1. Say what one cell means: dp[r][c] is the answer for the part of the grid that ends at (r, c).
  2. Find the base cases: the first row and the first column, where only one move leads in.
  3. Write the transition from the last move: here dp[r][c] = dp[r - 1][c] + dp[r][c - 1].
  4. Fill the table in an order where every cell a cell reads is ready: row by row, left to right.
  5. Take the answer from the last cell. A cell reads only its own row and the row above, so one row updated in place is enough.

Variant: Best subarray

The same, but the answer fits in one number: the best sum of a stretch that ends here. Such a stretch either extends the previous one or starts afresh if what is behind it is a loss.

  1. Keep two numbers: here, the best sum of a run that ends at the current index, and best, the largest here so far.
  2. At each number pick the larger: extend the run (here + x) or start a new one at x.
  3. Update best after every step, and return it at the end.
  4. Circular array: the answer is either an ordinary run, or the total minus the smallest run, found the same way with min. If every number is negative, keep the ordinary one.
  5. Single buy and sell of a stock is the same idea: keep the lowest price so far and check the profit of selling today.

Variant: Two strings

The same, but for two strings: a table cell is the answer for the start of one string and the start of the other. That is how you count the edits needed to turn one string into another.

  1. Make a table with one row per prefix of the first string and one column per prefix of the second, the empty prefix included.
  2. Fill the edges: turning a prefix into an empty string, or the reverse, takes as many edits as it has letters.
  3. For every other cell, compare the last letters and read the diagonal, the cell above and the cell to the left.
  4. The answer is in the bottom-right cell. Walk the arrows back to recover the edits themselves.
  5. Longest Common Subsequence and Interleaving String use the same prefix table, only the rule for a cell changes.

Variant: States

The same, but at each moment you are in one of a few states, such as holding a share or not. Keep the best result for each state, and get today's states from yesterday's.

  1. List the states you can be in at the end of a day, and what moves you from one to the next.
  2. For each state keep one number: the best money you can have in it after today.
  3. Each day, every state takes the larger of staying as it was and coming from the previous state with today’s price.
  4. At most k trades: keep arrays buy[1..k] and sell[1..k] and update them the same way, O(n·k) time.
  5. Unlimited trades: only two states, hold and free. hold = max(hold, free - p), free = max(free, hold + p).

Where it's used

  • Line breaks in TeX. TeX chooses where to break lines for the whole paragraph at once: for each possible break it remembers the best way to get there.
  • Comparing DNA. The Needleman–Wunsch and Smith–Waterman algorithms line up two DNA sequences with a table where each cell is the best answer for the starts of the two sequences. EMBOSS has them as needle and water.
  • Mobile networks and Wi-Fi. The Viterbi algorithm decodes a noisy signal: for each step it keeps the best path to every state instead of trying every sequence.