State, Witness, and Resource Contracts

A recurrence is a specification of smaller questions. A table is one implementation. Before coding, complete a state card:

Field	Required content
Input	Domain, identity, allowed sizes, fixed versus mutable data
Feasible object	Exact constraints and empty-object policy
State meaning	One sentence naming every coordinate and what it summarizes
Recurrence	Exhaustive legal decisions and combination rule
Boundary	Empty, impossible, zero-valued and terminal cases
Order	A rank or explicit dependency order; prerequisite arrow direction
Answer	Which cell or aggregation answers the original question
Witness	Representation, reconstruction rank and tie policy
Cost	States, transitions, arithmetic model, peak live data and output
Verification	Tiny oracle, independent witness checks and changed assumption

Four proof obligations

1. Sufficiency: histories merged into one state have equivalent relevant futures, or one dominates the other under the stated objective.
2. Soundness: each recurrence candidate composes a feasible object.
3. Completeness: every feasible object belongs to a represented decision case.
4. Evaluation: bases are correct and dependencies are ready; induction therefore transfers correctness to the requested answer.

For counting, prove that decision cases are disjoint or explicitly account for overlap. For optimization, independently checking a feasible witness shows attainability, not necessarily optimality. Exhaustive tiny oracles test the optimum; the general proof still comes from the recurrence and assumptions.

Impossible is not zero

At-most knapsack admits an empty value-0 selection at every capacity. Exact-fill knapsack has only capacity 0 reachable before processing items. A negative-reward grid can have a valid negative optimum. A missing TSP tour is returned as (None, []); a one-city tour has defined cost 0. Choose markers that cannot collide with legitimate numeric values, and never add them as if they were numbers.

Output preservation

LIS returns original indices, edit distance returns alignment columns, knapsack and schedules return object IDs, matrix chain returns a binary tree, tree DP returns chosen vertices, and TSP returns a closed route. Digit counting returns a count with explicit zero/range semantics. Accept any optimum unless a stronger tie-breaking requirement is explicitly taught and tested.

Rolling a value table can invalidate reconstruction. One-array knapsack parent links are especially dangerous: a predecessor capacity can later be overwritten by the same item. The core lab keeps full item layers. If you optimize it, explain how the witness still refers to the correct historical state and account for all retained records.

Numeric and resource model

Lab numeric inputs are exact Python integers, excluding booleans. Floating-point weights, overflow-prone fixed-width arithmetic and NaN need different contracts. Unit-cost analyses count arithmetic operations; enormous weights or counts require a separate bit-cost account. Python's integer/string conversion and memory limits still apply. No API promises to fit every mathematically valid input into memory.

Estimate cells and transitions before experiments. For edit strings of lengths 100,000 each, a full table has roughly 10 billion cells. For a rectangular n=20 TSP table there are 20,971,520 slots. Eight bytes per slot is only a representation estimate; object overhead, parents and outputs add more. Report measured environment and peak-memory method rather than inventing universal limits.

Independent use of tools

Standard lists, dictionaries, sets, sorting and binary search are allowed primitives. Implement recurrences yourself; do not delegate to the reference or an optimization library. Keep your first derivation, any external or AI help, a failing case and the repaired explanation. Tests passing is evidence about tested cases, not proof of independent authorship, asymptotic performance or mastery on unseen problems.