ToolSphere

Dynamic Programming Table Solver

Computer science

Solve dynamic programming tables step by step for 0/1 knapsack, LCS, edit distance and coin change. Inspect each recurrence and trace an optimal path.

0/1 knapsack · final answer

Maximum value: 7

Selected item numbers: 1, 2

Restart the table to practice each cell. This final answer stays visible while you step.

Each item can be used once. Up to 20 items; positive integer weights up to 100, nonnegative values up to 1,000,000; capacity 0–100.

30 of 30 cells filled, including base cases.

Selected cell D[4,5] = 7

max(skip D[3,5]=7, take 6 + D[3,0]=0) → 7. Ties skip.

Skip item 4 → D[3,5]

Rows: first i items. Columns: capacity. Fill order: left to right, then next row. Select any filled cell to inspect it.

0/1 knapsack table. Outlined cells form one traceback path; selected cell has a filled background. Infinity means unreachable.
i / j012345
0: no items
1: w=2, v=3
2: w=3, v=4
3: w=4, v=5
4: w=5, v=6

Traceback

Outlined cells follow one optimal path from the final cell back to a base case. The selected cell uses a solid background. Ties can produce other correct paths.

  1. D[4,5] = 7: Skip item 4 → D[3,5]
  2. D[3,5] = 7: Skip item 3 → D[2,5]
  3. D[2,5] = 7: Take item 2 → D[1,2]
  4. D[1,2] = 3: Take item 1 → D[0,0]
  5. D[0,0] = 0: Base case

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Dynamic Programming Table Solver

  1. 1Choose a problem to load its worked example, then edit the strings, items or coin denominations.
  2. 2Read the final answer above the inputs. Restart table and press Next cell to practice the row-by-row fill.
  3. 3Select any filled cell to see its recurrence, candidate values and chosen predecessor.
  4. 4Fill all cells to highlight one optimal traceback and follow its choices back to a base case.

About Dynamic Programming Table Solver

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.

Frequently asked questions

Which dynamic programming problems can I solve?

Choose 0/1 knapsack, longest common subsequence (LCS), unit-cost Levenshtein edit distance or unlimited minimum coin change. Each mode shows its table, selected-cell recurrence and one optimal traceback.

How do I fill the table one cell at a time?

Press Restart table, then Next cell. Base cases are included in the row-by-row fill order. Fill all cells completes the table; the final answer remains visible above the form while you practice.

Why does my traceback differ from the solver?

Several optimal paths can tie. This solver uses fixed tie rules shown in the selected-cell explanation. A different path can be correct if it has the same optimal value and obeys the recurrence.

Can I reuse items in the knapsack solver?

No. This is 0/1 knapsack: each item is available once. Weights must be positive whole numbers and values must be nonnegative whole numbers. Taking an item always refers to the previous row.

Is LCS the same as longest common substring?

No. A subsequence can skip characters while preserving their order. A substring must be consecutive. This tool computes a subsequence and displays one possible optimal sequence.

What edit operations and costs are supported?

Insert, delete and replace each cost one; matching costs zero. Adjacent transposition and custom costs are not supported. The actions describe an alignment, without mutable string indexes.

Does coin change count combinations?

No. It finds the minimum number of coins with unlimited reuse of each denomination. The table can show infinity for unreachable intermediate amounts or no solution for an unreachable target.

Can I enter empty strings or a zero target?

Yes. Empty strings are valid for LCS and edit distance. Knapsack capacity and coin target can be zero. Blank numeric fields are incomplete and clear the answer instead of silently becoming zero.

What are the input limits?

Use at most 20 items or distinct coin denominations. Weights and denominations are integers from 1 to 100; values range from 0 to 1,000,000; capacity and target range from 0 to 100. Each string can contain up to 24 Unicode code points.

Are capitalization and spaces ignored?

No. Strings are case-sensitive, and spaces count as characters. Comparison uses Unicode code points rather than whole visual grapheme clusters, so combining marks and multi-part emoji may occupy multiple positions.

Have a suggestion for Dynamic Programming Table Solver?Share your feedback ↗