Dynamic programming: knapsack, grids and strings interview questions

Both describe paying an amount of 0. It takes no coins, so the fewest-coins row stores 0 there, and every other entry is 1 + the entry of a smaller amount, so that 0 is what every one-coin answer is built on. There is exactly one way to pay 0, the empty payment, so the counting row stores 1, and every collection is that empty payment with coins added; with ways[0] = 0 every count would stay 0. The other entries start differently too: the fewest-coins row marks the amounts it has not paid yet as unreachable, while the counting row starts them at 0 ways.

With moves right or down, every route into a cell comes from the cell above it or the cell to its left, and both come earlier in row-by-row, left-to-right order, so each entry reads only entries that are already final. The cells and moves form a graph without cycles, and that order is a topological order of it. When moves may also go left or up, a route can come back to a cell, so routes can loop for ever, a cell's answer would depend on itself, and no filling order exists. Such problems ask for something else, usually the fewest moves, which breadth-first search finds.

A substring is a contiguous run of characters, while a subsequence keeps the order but may skip characters. For TAMARIND and MANDARIN the longest common substring is ARIN, four letters side by side in both words, while the longest common subsequence has five letters, MARIN or AARIN, picked with gaps. The two tables differ in one rule: for a subsequence, a mismatch takes the better of the cell above and the cell to the left, and the answer is the last cell; for a substring, a mismatch resets the cell to 0, and the answer is the largest cell anywhere. A line diff needs the subsequence, because the lines that both versions keep are usually separated by inserted and deleted lines.

It counts insertions, deletions and replacements of single characters, each costing 1, and keeping an equal character is free. For the bound, let the strings have lengths n ≤ m. Replace each of the first n characters of the shorter string that differs from the character at the same position in the longer one, then insert the remaining m − n characters: at most n + (m − n) = m edits. The distance is also at least m − n, because every edit changes the length by at most one. Mysore and Mysuru, both of six letters, are 2 edits apart, two replacements, and the distance is 0 only for identical strings.

A palindrome of odd length has a middle character, and one of even length has a middle gap between two characters. A string of n characters has n characters and n − 1 gaps between neighbours, so there are 2n − 1 possible middles, and each palindromic substring has exactly one of them. Expanding only around characters finds the odd palindromes and misses every even one: in GG it counts G twice but never GG, two instead of three, and in ABBA it misses BB and ABBA. One loop over c from 0 to 2n − 2, starting with lo = c // 2 and hi = lo + c % 2, covers both kinds: even c starts on a character and odd c on a gap.

A star can cover any run of the name that ends at the current character, and trying every start of that run would cost O(n) per cell. The cell above already holds the answer for runs that end one character earlier: it is true when the star, with the mask before it, can cover the name up to the previous character. If the star's run is not empty, dropping its last character leaves such a shorter run, so the cell above is true. If the run is empty, the mask without the star must match the same name, which is the cell to the left. Those two cells cover every possible run, so each cell costs O(1) and the whole table O(nm).

Because the table only compares letters. Cell (i, j) asks whether a[:i] and b[:j] merge into c[:i + j], so the answer cell (n, m) looks at c[:n + m] and nothing beyond it. If c is longer, its extra letters at the end are never read, and a broadcast with additions would pass. If c is shorter, reading c[i + j − 1] runs past its end and crashes, or a loop that stops at the end of c reports a merge that drops letters. An interleaving uses every letter of both strings exactly once, so the lengths must add up, and checking that costs O(1). For a = PQR and b = XY, the broadcast PXQY has 4 letters instead of 5, so the answer is false at once.

One way stores a choice for every state while the table is filled: the coin, item or move that produced its value. Rebuilding then follows the stored choices from the final state, one step per part of the answer and with no comparisons, at the price of a second array as large as the table. The other way keeps only the values and recomputes each choice during the walk: a transition belongs to an optimal answer exactly when it reproduces the stored value, as when best[a − c] equals best[a] − 1 for a coin c. That needs no extra memory and a few comparisons per step. Either way, choose the tie rule on purpose, because several transitions can reproduce the same value.