When a big problem breaks into smaller ones that repeat, solve each small one once, write the answer in a table, and build up. Every cell is filled from cells already filled. That's the whole idea, and it turns exponential searches into a single pass over a grid.
How many single-letter edits (insert, delete or substitute) turn one word into another? Cell (i, j) holds the answer for the first i letters of the top word and the first j letters of the side word. Spell checkers, diff and DNA alignment all use this table.
How to read this: each cell compares the start of one word with the start of the other: the fewest edits between them, or in the longest-common-subsequence mode, how many letters they share in order. A cell is filled from the three cells above and to its left, and the bottom-right cell is the answer. ε means the empty start, before any letters.
A bag holds a set weight. Each item is all-or-nothing. Which items give the most value? Row i uses the first i items and column w is a bag of capacity w. Each cell makes one choice: leave item i out, or put it in and use the best bag for the weight that's left.
How to read this: each cell is the most value ($) that fits in a bag of that many kg (the column), using only the items in that row and above. "6·30" after an item means 6 kg, worth $30.
A tempting shortcut is to grab the best value per kilogram first. It's fast, but it can strand space in the bag.
Each entry is the sum of the two above it, so the whole triangle is a DP table for C(n, k), the number of ways to choose k things from n. Color the entries by their remainder and a fractal appears: odd entries trace the Sierpiński triangle.
How to read this: each little cell is one number in Pascal's triangle, and each is the sum of the two cells above it. In the Mod modes, a cell's color is the remainder left after dividing by 2, 3, 5 or 7. In Size, dark green is a small number and bright yellow a very large one.
Try this: drag Rows to 256 in Mod 2.
Computing C(n, k) with plain recursion asks for the same entries over and over. The number of calls is 2·C(n, k) − 1, which grows exponentially. Filling the triangle row by row computes each entry once, using about n²/2 additions.
The two counters compare both methods for the middle of the bottom row. Hover any entry to see its value.
C(n, k) is odd exactly when every 1-bit of k is also a 1-bit of n. That rule repeats at every power of 2, which is why mod 2 gives a perfect self-similar fractal. Any prime modulus gives a similar fractal with that many copies at each level.