---
title: "Dynamic programming"
description: "Subset dynamic programming searches combinations of tensor subsets; interval dynamic programming selects a parenthesization for a fixed leaf order."
eyebrow: "Path-finding algorithms"
---

## Two forms of dynamic programming {#state-spaces}

Dynamic programming (DP) solves small subproblems first, then uses their results to solve larger ones. ArcTN defines states in two ways:

| Method | What one state represents | Search space |
| --- | --- | --- |
| `optimal_dp` | A connected tensor subset | Permitted binary splits of that subset |
| `order_dp` | A contiguous interval in a given leaf order | Binary parenthesizations preserving the leaf order |

The methods use different states: `optimal_dp` is subset DP, while `order_dp` is interval DP.

## Subset dynamic programming {#optimal-dp}

Let $C(S)$ be the minimum cost of contracting tensor set $S$. Let $\mathcal P(S)$ denote the permitted splits in the current search space: $A$ and $B$ are nonempty valid subproblems satisfying $A\cup B=S$ and $A\cap B=\varnothing$. The total cost is the cost of contracting each side plus the cost of merging them:

$$
C(S)=\min_{(A,B)\in\mathcal P(S)}
\bigl[C(A)+C(B)+c(A,B)\bigr].
$$

$c(A,B)$ is computed using the current [optimization objective](/docs/path-metrics#definition), not the local greedy score.

```pseudocode
Initialize table entries for single tensors
Process connected subsets S in increasing tensor count:
    Enumerate valid left/right splits (A, B) of S
    C[S] = minimum(C[A] + C[B] + c(A, B))
    Save the split yielding this value
Backtrack each component contraction tree using the best split
Merge component roots using outer-product dynamic programming
return the complete path
```

The exactness of `optimal_dp` is limited to this search space: connected subsets are contracted first, then disconnected components are merged. It does not enumerate all trees that permit outer products at arbitrary intermediate steps. The number of states grows rapidly with network size, so this method suits small networks. `max_n` limits the tensor count of the entire input network.

## Interval dynamic programming for a fixed leaf order {#order-dp}

Given leaf order `[A, B, C, D]`, the method can compare parenthesizations such as `((AB)C)D` and `(AB)(CD)`, but cannot change the leaf order to `[A, C, B, D]`.

```diagram
order-dp-transition
Each split divides a contiguous interval into left and right parts. The figure shows the three split points for the four-tensor interval; each part reuses its previously computed best result.
```

For interval $[i,j]$, enumerate split points $k$:

$$
C(i,j)=\min_{i\le k<j}
\left[C(i,k)+C(k+1,j)+c([i,k],[k+1,j])\right].
$$

```pseudocode
Initialize table entries for single-tensor intervals
Process intervals [i, j] in increasing length:
    Enumerate split points k = i, ..., j-1
    C[i,j] = minimum(left cost + right cost + merge cost)
    Save the best split point
return the path backtracked from the complete interval
```

`order_dp` chooses the best parenthesization for the given leaf order, with no guarantee over all leaf orders. It has $O(n^2)$ intervals and $O(n^3)$ candidate splits, plus the cost of processing index sets.

## Interfaces and uses {#interfaces}

Use `optimal_dp` for small networks and `order_dp` to adjust the parenthesization of an existing leaf order. `leaf_order_of_path` extracts a leaf order from a complete path. See the [Rust API](/docs/rust-api#path-search) for signatures and objective parameters.

### Relationship to hypergraph bisection {#bisect}

[Hypergraph bisection](/docs/bisection#bisect) recursively partitions the network and calls subset DP for sufficiently small subproblems.