Dynamic programming

algo has dedicated syntax for dense dynamic programming tables and a memoization decorator for top-down recurrences.

DP blocks

The general form is:

dp[dimensions] -> type, strategy:
    base: ...
    <- candidate

Example:

input:
    n: int

dp[i: 2..n] -> int, assign:
    base: dp[0] = 0
    base: dp[1] = 1
    <- dp[i-1] + dp[i-2]

println dp[n]

What each part means:

• i: 2..n: loop variable and inclusive range
• -> int: cell type
• assign: how candidates combine
• base:: cells initialized before the main recurrence
• <-: a candidate value for the current cell

Strategies

Strategy	Typical use
maximize	knapsack, LIS
minimize	shortest/edit-style DP
sum	counting ways
any	reachability / boolean DP
assign	direct recurrences

Example: 0/1 knapsack

input:
    n, W: int
    w: [int][n]
    v: [int][n]

dp[i: 1..n, j: 0..W] -> int, maximize:
    base: dp[0][j] = 0
    <- dp[i-1][j]
    <- dp[i-1][j-w[i-1]] + v[i-1] where j >= w[i-1]

println dp[n][W]

Use where when a candidate is only valid under a guard condition.

Example: LIS transition

input:
    n: int
    a: [int][n]

dp[i: 0..n-1] -> int, maximize:
    base: dp[i] = 1
    <- dp[j] + 1 for j in [0, i) where a[j] < a[i]

println max(dp[i] for i in [0, n))

Use for ... where ... on a candidate when the transition itself needs a nested loop.

Rolling DP

For row-by-row DP, add rolling:

dp[i: 1..n, j: 0..W] -> int, maximize, rolling:
    base: dp[0][j] = 0
    <- dp[i-1][j]
    <- dp[i-1][j-w[i-1]] + v[i-1] where j >= w[i-1]

println dp[n&1][W]

Use this when the recurrence only depends on the previous row and you want to reduce memory usage.

Manual DP still works

If a problem shape does not fit the dp block cleanly, write the loops directly:

dp = filled(n + 1, filled(cap + 1, 0))
for i in [1, n]:
    for j in [0, cap]:
        dp[i][j] = dp[i-1][j]
        if j >= w[i-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1])

Memoized recursion with @memo

Use @memo for sparse state spaces or naturally recursive transitions:

@memo
fn solve(i: int, rem: int) -> long:
    if i == n:
        if rem == 0: 1
        else: 0
    elif rem < 0:
        0
    else:
        solve(i + 1, rem - a[i]) + solve(i + 1, rem)

Choosing between the two

• Use dp blocks for dense table DP and iteration-friendly recurrences
• Use rolling when only adjacent layers matter
• Use @memo when the state space is sparse or recursive structure is clearer
• Fall back to manual loops when the problem does not fit the syntax naturally