Work through a dynamic programming table
This dynamic programming table solver helps you practice four common Intro to Algorithms problems: 0/1 knapsack, longest common subsequence, edit distance and minimum coin change. Choose a problem, edit its inputs and read the final answer above the form. A completed example loads immediately. Restart the table when you want to calculate each cell yourself, then compare your work with the recurrence shown beside the selected cell.
The table includes its base row and column. Cells fill from left to right across each row before moving downward. Click or tap any filled cell to inspect the candidate values used to compute it. Once the table is complete, outlined cells show one optimal traceback. A solid background marks your selected cell. On a phone, scroll within the table to reach later columns; the rest of the page stays within the screen.
Start with a precise state definition
Before filling cells, say what D[i,j] means. In knapsack it is the best value using the first i items with capacity j. For LCS it is the length of a longest common subsequence of the two prefixes. For edit distance it is the minimum cost of changing the first string’s prefix into the second string’s prefix. In coin change it is the fewest coins needed to make amount j using the first i denominations.
These meanings explain the borders. An empty prefix has LCS length zero. With no items or zero capacity, knapsack value is zero because weights must be positive. Edit distance along a border counts the characters inserted or deleted. Coin change starts with zero coins for amount zero, while a positive amount with no available denominations is unreachable. The symbol ∞ marks that unreachable state.
A worked 0/1 knapsack example
The loaded weights are 2, 3, 4 and 5, with corresponding values 3, 4, 5 and 6. Capacity is 5. The computed maximum value is 7, obtained by choosing item numbers 1 and 2. Their combined weight is 5. The last cell compares skipping the fourth item, which preserves value 7, against taking that item for value 6 plus the zero-capacity result. Skipping wins.
When an item fits, compare D[i−1,j] against value[i] + D[i−1,j−weight[i]]. Both choices use the previous row, so an item cannot be reused. When the weight exceeds the current capacity, copy the previous row. Traceback moves to the previous row each time; a diagonal jump in capacity identifies a selected item. Equal candidates prefer skipping, so different optimal item sets may exist even though this tool displays only one.
Longest common subsequence
For ABCBDAB and BDCABA, the computed LCS length is 4 and the displayed subsequence is BCBA. A subsequence preserves order but can skip characters; it does not have to occupy consecutive positions. If the current characters match, add one to the diagonal predecessor. If they differ, take the larger value from above or left. This tool moves upward on a tie.
Read the matching characters along the traceback in reverse to recover the subsequence. Skipping a row or column character does not add to its length. Capitalization and spaces matter. Strings are compared by Unicode code point, so a multi-code-point emoji or an accented character written with a combining mark can occupy more than one position.
Edit distance with unit costs
Changing kitten to sitting has computed edit distance 3: replace k with s, replace e with i, then insert g. The recurrence compares a diagonal match or replacement, a deletion from above and an insertion from the left. Matching costs zero; each other operation costs one. Ties prefer the diagonal, then deletion, then insertion.
This is Levenshtein distance. Swapping neighboring characters is not a separate operation, and there are no custom operation weights. The displayed actions describe an alignment in forward order; they are not a script with changing character indexes. Empty strings are valid and demonstrate why the border values are needed.
Minimum coin change with unlimited reuse
For denominations 1, 3 and 4 and target 6, the computed answer is 2 coins: 3 + 3. This example shows why taking the largest available coin first can fail. The recurrence compares skipping the current denomination against taking one coin plus the result for the remaining amount. Taking a coin stays on the same row, allowing repeated use.
This mode minimizes the number of coins. It does not count combinations and does not impose a limited coin inventory. Unreachable targets show no solution and have no traceback. Duplicate denominations are rejected so every row has a distinct meaning. Input limits keep the table readable for homework: at most 20 items or denominations, capacities and amounts through 100, and strings through 24 code points.
Use the result to check your reasoning
Write your state, base cases and recurrence before revealing cells. Follow the dependency coordinates and explain why every dependency is already available. Then distinguish the numeric optimum from the particular choices returned by traceback. Full tables use space proportional to their displayed cells; this teaching view deliberately retains those cells rather than using a memory-saving implementation. Continue in the Algorithms Lab for recurrence practice and Huffman coding.