---
title: "dynamic-programming-optimization — Mova code model"
description: "Mova code model of models/dynamic-programming-optimization.groupant: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/models/dynamic-programming-optimization.groupant/"
---
Elamur: [Mova](https://md.mova.elamur.ai/free/en/) · [Dictionary](https://md.dictionary.elamur.ai/free/en/) · [Research](https://md.research.elamur.ai/free/en/) · **Groupants**

This page as HTML: <https://groupants.elamur.ai/free/en/mova/models/dynamic-programming-optimization.groupant/>

# dynamic-programming-optimization

The groupant beside models/dynamic-programming-optimization.groupant in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

## Facts

- **kind:** groupant_group
- **status:** partial source bound group
- **bound sources:** 10
- **repository folder:** [`models/dynamic-programming-optimization.groupant`](https://github.com/ElamurAI/mova-free/tree/main/models/dynamic-programming-optimization.groupant)
- **repository commit:** `855da7bd4a7b`

> **Implementation material.** A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.

## Components

| component | label | where |
|---|---|---|
| **approximant** | partial source model | [forward](#forward) |
| **ast** | not materialized |  |
| **composition** | partial source model | [composition](#composition) |
| **cost** | partial source model | [cost](#cost) |
| **descriptant** | partial source model | [epoch-memory](#epoch-memory) |
| **invariant** | partial source model | [invariant](#invariant) |
| **tests** | bounded executed | [checks](#checks) |

## Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

| id | type | label | where |
|---|---|---|---|
| `dynamic-programming-optimization-behavior-complement` | behavior_complement | partial source model | [behavior-complement](#behavior-complement) |
| `dynamic-programming-optimization-reverse-reconstruction` | reverse_reconstruction | partial source model | [reverse-reconstruction](#reverse-reconstruction) |
| `dynamic-programming-optimization-subset-embedding` | attainability_objective_relation | partial source model | [subset-embedding](#subset-embedding) |
| `dynamic-programming-optimization-monotone-reduction` | conditional_search_restriction | partial source model | [monotone-reduction](#monotone-reduction) |
| `dynamic-programming-optimization-tree-recurrence` | interval_root_restriction | partial source model | [tree-recurrence](#tree-recurrence) |

## Model text


### model

## dynamic-programming-optimization

### forward

Exact integer subset/knapsack objectives and structured matrix/partition/tree dynamic programming with explicit work and allocation bounds.

### invariant

Exact feasible objectives, caller structural assumptions, checked integer arithmetic and leftmost ties retain distinct contracts. Resource errors never masquerade as approximation.

### cost

Bitset O(n*ceil((T+1)/64)) packed work; MITM O(2^(n/2) log2^(n/2)); SMAWK O(rows+cols) callbacks; partition O(layers*n*log n); Knuth O(n²). Callback/allocations count and caps remain leaf-specific.

### composition

Weight=profit subset embedding links target reachability with attainable knapsack objectives. Totally-monotone identity minima transport coordinates into convex interval costs and positive BST weights in the harness.

### epoch-memory

Wave20, 2026-10-30. Models retain real-arithmetic assumptions separately from native finite checks. Kernels are library tools, not automatically adopted into training or inference.

### checks

["bitset_and_mitm_join_exhaustive_attainable_objectives","smawk_partition_and_knuth_join_independent_dp_oracles"]

### limitations

SMAWK every submatrix must have monotone leftmost minima; merely full-matrix monotone minima is insufficient. Partition monotone optima must hold at every layer. These properties are not verified dynamically. BST is successful-key-only objective.

### catalog

## Typed family relations

Each relation keeps its own domain and assurance.

### behavior-complement

Type: behavior_complement.

For exact integer targets, exclude a bitset true decision with no subset summing to target, a knapsack objective unattainable under capacity or below the feasible maximum, a SMAWK column that is not the leftmost row minimum, a partition value violating the minimum over exactly the requested nonempty contiguous intervals, or a BST value violating the successful-key interval recurrence. SMAWK/partition exclusions are conditional on total-monotonicity/monotone-split premises: arbitrary callbacks outside those premises may yield incorrect answers without validation errors. Native categorical exclusions also include overflow wraparound, violating word/state/cell or callback caps, and returning partial answers on budget failure. These integer targets do not carry f64 tolerances.

### reverse-reconstruction

Type: reverse_reconstruction.

A reachability true output retains all item multisets having at least one target-sum subset; false retains those having none. For [1,1] at target1, two distinct index masks share the same decision and knapsack objective, and objective-only output does not recover either witness. Fixed SMAWK minima j_i constrain each lawful row by M[i,j_i]<=M[i,j] and strict inequality for earlier j on ties; row offsets preserve minimizer indices while changing values. A partition scalar retains many interval-cost arrays and boundary choices, subject to nonempty contiguous ranges and structural premises; it does not reconstruct a split witness. BST cost similarly admits different weight vectors or tied optimal trees. Checked integer values are exact when successful under the stated premises, while an error identifies only a broad resource/domain fiber.

### subset-embedding

Type: attainability_objective_relation.

Embedding each v as weight=v,value=v gives feasible objectives equal to subset sums<=capacity. Decision(target) is true iff optimum(target)=target, provided both resource domains admit input. Many masks may give the same objective.

### monotone-reduction

Type: conditional_search_restriction.

SMAWK elimination is valid for total monotonicity with left ties; divide/conquer recursion restricts split search using nondecreasing leftmost optimal indices. Violating premises may silently yield wrong results, not a validation error.

### tree-recurrence

Type: interval_root_restriction.

For nonnegative successful-key weights, C[i,j]=sum(w[i..j])+min_r(C[i,r]+C[r+1,j]); Knuth monotone root bounds reduce cubic root enumeration to quadratic. Equal costs can retain multiple trees; harness compares independent full enumeration.

### wave20-evidence

#### Family evidence — 2026-10-30

This family binds ten implementation/test sources. Named joins ["bitset_and_mitm_join_exhaustive_attainable_objectives","smawk_partition_and_knuth_join_independent_dp_oracles"] in algorithms/tests/composition_wave20.rs pass four times within the 695-check algorithm suite.

Forward: Exact integer subset/knapsack objectives and structured matrix/partition/tree dynamic programming with explicit work and allocation bounds.

Invariant: Exact feasible objectives, caller structural assumptions, checked integer arithmetic and leftmost ties retain distinct contracts. Resource errors never masquerade as approximation.

Cost: Bitset O(n*ceil((T+1)/64)) packed work; MITM O(2^(n/2) log2^(n/2)); SMAWK O(rows+cols) callbacks; partition O(layers*n*log n); Knuth O(n²). Callback/allocations count and caps remain leaf-specific.

Assumptions: SMAWK every submatrix must have monotone leftmost minima; merely full-matrix monotone minima is insufficient. Partition monotone optima must hold at every layer. These properties are not verified dynamically. BST is successful-key-only objective.

[Integrated evidence](https://md.groupants.elamur.ai/free/en/mova/models/algorithm-library.groupant/#wave20-evidence) records actual receipts. Leaf oracles remain separate from cross-implementation agreement; family membership cannot verify unchecked callback premises or a shared error budget.