{{ summaryTitle }}
{{ summaryValue }}

{{ summaryLine }}

States{{ resultsReady ? result.counts.computedStates : '—' }} Events{{ resultsReady ? result.trace.length : '—' }} Memo hits{{ resultsReady ? result.counts.cacheHits : '—' }}
Switching the problem changes its inputs, recurrence, state table, chart, and trace ledger.
Both strategies solve the same problem; their event profiles and evaluation orders differ.
Use a whole-number index from 0 to 18.
{{ issueMessage('fib_n') }}
The neutral default is off; all canonical recurrence data remains available to exports.
{{ show_full_recurrence ? 'Shown in the trace ledger' : 'Hidden for a compact ledger' }}
Solution brief
{{ row.label }}
{{ row.value }}
Canonical recurrence
The answer, state table, chart, ledger, and exports consume this same evaluated result.
{{ result.recurrence }}
{{ result.reconstruction }}
State{{ label }}Copy
{{ row.label }}{{ cell.display }}

The chart renderer is unavailable. Event counts remain available in the solution brief and trace ledger.

StepEventStateDecisionRecurrenceCopy
{{ event.index + 1 }}{{ eventKindLabel(event.kind) }}{{ shortStateKey(event.stateKey) }}{{ event.chosen || event.explanation }}{{ event.recurrence || '—' }}
Recursion & Backtracking Simulator Trace four recursion and backtracking presets step by step with synchronized call stacks, branch choices and clear return and undo events.
String Matching Algorithm Simulator Compare four exact string-matching methods with Unicode traces showing preprocessing and shifts plus overlap and hash-collision handling.
Pathfinding Algorithm Simulator Compare four pathfinding algorithms on an editable weighted grid and inspect route cost, exploration order, diagonal rules and no-path outcomes.
Sorting Algorithm Simulator Step through eight sorting algorithms on entered or seeded arrays with verified order, stability and operation counts for each deterministic run.

Some problems appear to branch into a large search, yet many branches ask the same smaller question. Dynamic programming avoids solving those repeated subproblems from scratch. It defines a state, expresses that state in terms of smaller states, stores each answer, and uses the stored results to build or reconstruct the final solution.

Two properties usually make the method useful. Overlapping subproblems means the same state is requested more than once. Optimal substructure means an optimal answer can be assembled from optimal answers to smaller states. Fibonacci numbers show repeated numeric dependencies, minimum coin change chooses the best predecessor amount, and longest common subsequence compares prefixes of two sequences.

  • Top-down memoization starts from the requested answer, follows recursive dependencies, and caches states as they are reached.
  • Bottom-up tabulation starts from base states and fills a table in an order that makes every dependency available before it is used.
  • Reconstruction follows stored choices after the numeric table is complete to recover coins or subsequence characters, not just an optimal length or count.

The two strategies should agree on the mathematical answer when they use the same recurrence and tie policy, but their traces differ. Top-down work reflects the states demanded by recursion and may show cache hits. Bottom-up work follows a fixed fill order and may compute states that the final path never visits.

Dynamic programming is not automatically the right answer to every recursive problem. A state definition can omit information, a recurrence can compare the wrong predecessors, and a correct value can still reconstruct a different equally optimal solution because of tie handling. The state meaning, base cases, transition, evaluation order, and traceback policy all need to agree.

How to Use This Tool:

Choose a problem and strategy together, then follow the state table from base cases to the requested answer.

  1. Select Fibonacci, Minimum coin change, or Longest common subsequence (LCS), then choose top-down memoization or bottom-up tabulation.
  2. Enter the problem-specific values: a Fibonacci index from 0 to 18, one to six distinct coin denominations with a target from 1 to 40, or two sequences of one to eight Unicode characters.
  3. Read the Solution brief for the answer, strategy, number of computed states, memo hits, and reconstruction steps. An unreachable coin target is reported without inventing a combination.
  4. Use the State table and trace ledger to connect each stored value with its dependencies. Turn on Full recurrence text when the decision column alone does not explain a transition.
  5. Run the same problem with the other strategy. The answer should agree; compare state order, memo hits, and event counts to see how evaluation changed.

Interpreting Results:

The final answer and reconstructed solution are the primary results. State and event counts describe this bounded trace, not elapsed runtime on a programming language or machine. A memo hit records reuse during top-down evaluation; zero memo hits is expected for bottom-up tabulation and does not make that strategy less correct.

  • Fibonacci returns the requested value and has no separate traceback.
  • Minimum coin change returns the fewest supplied coins or reports the target unreachable. When equal-length choices exist, the larger denomination is preferred.
  • LCS returns a length and one reconstructed subsequence. Several different subsequences may have the same maximum length; equal predecessor lengths prefer the upper table cell.
  • Compare strategies only with the same problem inputs. Different state counts can be legitimate because top-down and bottom-up visit states in different ways.

Technical Details:

A dynamic-programming state is a complete description of one smaller question. The recurrence lists the predecessor states needed to answer it, while base states stop the dependency chain. Values are evaluated with exact integer arithmetic within the bounded inputs, and deterministic tie rules make reconstruction repeatable.

Formula Core:

Fibonacci uses two base states and adds the preceding two values.

F0=0,F1=1,Fn=Fn-1+Fn-2

For minimum coin change, C(a) is the fewest coins needed to make amount a. Only supplied coin values c with a reachable predecessor are considered; an unreachable state is treated as infinity.

C0=0,Ca=minc∈D,c≤a1+Ca-c

For LCS, L(i,j) is the maximum subsequence length shared by the first i characters of the left sequence and first j characters of the right sequence.

Li,j=0if i = 0 or j = 01+Li-1,j-1if the current characters matchmaxLi-1,j,Li,j-1otherwise

Mechanism Core:

StageTop-down memoizationBottom-up tabulation
Starting pointThe requested final state.All required base states.
Evaluation orderRecursive demand order.A fixed dependency-safe table order.
Reuse evidenceA memo hit when a stored state is requested again.Direct table reads; no memo-hit event is counted.
ReconstructionFollow stored coin or predecessor choices from the final state toward a base state.

Coin denominations are normalized into descending order, which supports the larger-denomination tie rule. LCS works on Unicode characters as sequence elements. The bounded problem sizes keep recursive traces and state tables readable; they are teaching limits rather than general algorithm limits.

Worked Examples:

A greedy coin choice is not always optimal

For denominations 1, 3, and 4 with target 6, taking the largest available coin first suggests 4 + 1 + 1. Dynamic programming evaluates smaller amounts and finds 3 + 3, so the minimum is two coins. Both strategies return that count, while their state order and memo-hit profile differ.

References: