# Algo Tabulation

> Bottom-up DP (tabulation) in Python: edit distance/Levenshtein, LCS, and LIS with rolling-array space optimization. Use when comparing DNA/protein sequences, scoring similarity, or filling a DP table without recursion.

- Skill: `pavel-kravchenko/algo-tabulation` (Agent Skill)
- Install (CLI): `npx skillmds@latest add pavel-kravchenko/algo-tabulation`
- Raw SKILL.md: https://api.skillmd.com/api/skills/pavel-kravchenko/algo-tabulation/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- Author: pavel-kravchenko (https://skillmd.com/u/pavel-kravchenko)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/pavel-kravchenko/algo-tabulation

---


# Tabulation (Bottom-Up Dynamic Programming)

## When to Use

- Comparing two strings/sequences and need an edit distance, alignment score, or LCS without pulling in a full aligner library
- Recursive/memoized DP hits `RecursionError` on long sequences and needs converting to an iterative table
- Need to quickly pre-screen candidate sequences by similarity before running expensive Needleman-Wunsch/Smith-Waterman alignment
- Finding the longest increasing trend in a numeric series (e.g., expression values over a time course)
- Need O(1) or O(min(m,n)) space instead of O(mn), because the sequences are long and only the final score (not full traceback) is needed

## Version Compatibility

Pure Python stdlib — no external dependencies. Works on Python ≥3.8 (uses only list comprehensions and tuple unpacking).

## Prerequisites

- Understand recursion + memoization first (see `algo-intro-memoization`)
- Comfortable with 2D list indexing and nested loops
- For biological alignment scoring (gap penalties, substitution matrices), see `algo-sequence-alignment` — tabulation here is the unweighted/uniform-cost special case

## Memoization vs Tabulation

| Aspect | Memoization (Top-Down) | Tabulation (Bottom-Up) |
|--------|----------------------|----------------------|
| Direction | Recurse down, cache results | Iterate up, fill table |
| Stack overflow | Risk with deep recursion | No risk |
| Subproblems solved | Only the ones needed | All subproblems |
| Space optimization | Harder (cache is sparse) | Easy (rolling arrays) |

**Goal:** Warm up with the classic O(1)-space rolling-variable pattern before applying it to sequences.
**Approach:** Keep only the last two values instead of a full table.

```python
def fib_optimized(n):
    """Bottom-up Fibonacci using O(1) space (two rolling variables)."""
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1
```

## Edit Distance (Levenshtein) with Traceback

**Goal:** Compute the minimum insert/delete/substitute operations to transform one DNA/protein string into another, and recover the actual operations (not just the count).
**Approach:** Fill `dp[i][j]` = edit distance between `s1[:i]` and `s2[:j]`, then walk backward from `dp[m][n]` re-deriving which transition produced each cell.

```python
def edit_distance_with_ops(s1, s2):
    """
    Compute Levenshtein distance and the traceback of edit operations.

    dp[i][j] = min edits to transform s1[:i] into s2[:j].
    Returns (distance, ops) where ops is a list of tuples:
      ('Match', c), ('Substitute', c1, c2), ('Delete', c), ('Insert', c)
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i  # delete all of s1[:i]
    for j in range(n + 1):
        dp[0][j] = j  # insert all of s2[:j]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete from s1
                    dp[i][j - 1],      # insert into s1
                    dp[i - 1][j - 1],  # substitute
                )

    # Traceback: re-derive which transition produced each cell
    ops = []
    i, j = m, n
    while i > 0 or j > 0:
        if i > 0 and j > 0 and s1[i - 1] == s2[j - 1]:
            ops.append(('Match', s1[i - 1])); i -= 1; j -= 1
        elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
            ops.append(('Substitute', s1[i - 1], s2[j - 1])); i -= 1; j -= 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(('Delete', s1[i - 1])); i -= 1
        else:
            ops.append(('Insert', s2[j - 1])); j -= 1

    ops.reverse()
    return dp[m][n], ops


distance, ops = edit_distance_with_ops("ATCG", "TACG")
assert distance == 2  # ops holds the Insert/Match/Delete trace that produced it
```

## Longest Common Subsequence (LCS)

**Goal:** Find the longest subsequence common to two sequences and use its length as a fast conservation/similarity score.
**Approach:** Same table shape as edit distance but maximizing matches instead of minimizing edits; traceback follows the larger neighbor.

```python
def lcs_with_traceback(s1, s2):
    """Return the longest common subsequence string of s1 and s2."""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            result.append(s1[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(result))


def lcs_similarity(s1, s2):
    """Quick conservation score in [0, 1]: LCS length / longer sequence length.

    ~1.0: highly conserved (e.g. orthologs in closely related species)
    ~0.5: moderate conservation (e.g. diverged paralogs)
    ~0.0: little shared structure
    Cheaper than a full Needleman-Wunsch/Smith-Waterman pass — good for
    pre-screening candidates before running an expensive aligner.
    """
    lcs_len = len(lcs_with_traceback(s1, s2))
    return lcs_len / max(len(s1), len(s2))
```

## Space-Optimized LCS Length — O(min(m,n)) space

**Goal:** Get the LCS *length* for long sequences without paying O(mn) memory.
**Approach:** Only the previous row is needed, so keep two 1D arrays instead of a full 2D table (loses traceback ability).

```python
def lcs_length_space_optimized(s1, s2):
    """LCS length using only two rows of size min(m,n)+1."""
    if len(s2) > len(s1):
        s1, s2 = s2, s1
    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev, curr = curr, [0] * (n + 1)
    return prev[n]
```

## Bonus: Longest Increasing Subsequence (LIS)

**Goal:** Find the longest increasing run in a numeric series, e.g. an increasing trend across gene-expression time points.
**Approach:** `dp[i]` = length of the LIS ending at index `i`; O(n²) tabulation (use `bisect` for O(n log n) if the series is long).

```python
def lis_length(arr):
    """Length of the longest strictly increasing subsequence, O(n^2)."""
    n = len(arr)
    if n == 0:
        return 0
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)


expression = [2.1, 3.5, 1.2, 4.8, 3.9, 5.2, 6.1, 4.5, 7.0]
assert lis_length(expression) == 6  # e.g. 2.1, 3.5, 4.8, 5.2, 6.1, 7.0
```

## Pitfalls

- Space-optimized DP (`lcs_length_space_optimized`) only recovers the optimal *value* — you cannot traceback the actual alignment/subsequence from it; use the full O(mn) table when you need the traceback
- `edit_distance_with_ops` checks `dp[i][j] == dp[i-1][j-1] + 1` for substitution before checking delete/insert — order matters when multiple operations tie, or the recovered path (though same cost) may differ from what you expect
- LCS and edit distance are related but not interchangeable: `edit_distance >= len(s1) + len(s2) - 2 * lcs_length`
- `lis_length` here is strictly increasing (`arr[j] < arr[i]`); switch to `<=` for non-decreasing subsequences
- O(n²) LIS is fine for a handful of time points; for genome-scale series use the O(n log n) patience-sorting variant with `bisect.bisect_left`

## See Also

- `algo-intro-memoization` — top-down recursive DP with caching, the counterpart to this bottom-up approach
- `algo-sequence-alignment` — weighted alignment with gap penalties and substitution matrices (BLOSUM/PAM), of which edit distance is the uniform-cost special case
- `algo-knapsack` — another classic tabulation problem (0/1 and unbounded knapsack)
- `bio-alignment-pairwise-alignment` — production pairwise alignment via Biopython/parasail instead of hand-rolled DP