Dynamic Programming: Recursive Formulations

A compendium of recursive functions for a few DP problems I encountered while solving algorithm problems. For each problem, we state the problem and give the recurrence that leads to a dynamic programming solution.

0-1 Knapsack

Problem. Given $n$ items, each with weight $w_i$ and value $v_i$, and a knapsack of capacity $W$, maximize the total value without exceeding $W$.

$$\maximize \sum_{i=1}^n v_i x_i \quad \st \quad \sum_{i=1}^n w_i x_i \leq W, \quad x_i \in \{0,1\}.$$

Recursion. Define $f(i, w)$ as the maximum value attainable with weight $\leq w$ using the first $i$ items.

$$f(i, w) = \begin{cases} 0 & \text{if } i = 0, \\ f(i-1, w) & \text{if } w_i > w, \\ \max\{f(i-1, w),\ f(i-1, w - w_i) + v_i\} & \text{otherwise.} \end{cases}$$

Answer: $f(n, W)$. Complexity: $O(nW)$.

Variations: bounded knapsack ($0 \leq x_i \leq c$), unbounded knapsack ($x_i \geq 0$).

Unbounded Knapsack

Problem. Same as 0-1 Knapsack, but each item can be used unlimited times: $x_i \geq 0$.

Recursion. Define $f(w)$ as the maximum value attainable with capacity $w$.

$$f(w) = \max_{i \,:\, w_i \leq w} \{ f(w - w_i) + v_i \}$$

with $f(0) = 0$. Answer: $f(W)$. Complexity: $O(nW)$.

Implementation note: iterate $w$ forward (unlike 0-1 where you iterate backward).

Bounded Knapsack

Problem. Each item $i$ has at most $c_i$ copies available: $0 \leq x_i \leq c_i$.

Recursion. Use binary lifting: split $c_i$ copies into groups of $1, 2, 4, \ldots, c_i - 2^k + 1$ copies, creating $O(\log c_i)$ virtual items. Then solve as 0-1 Knapsack.

Complexity: $O(W \sum_i \log c_i)$.

Coin Change

Problem (min coins). Given coins of denominations $c_1, \ldots, c_n$ (unlimited supply), find the minimum number of coins to make amount $W$.

Problem (count ways). Count the number of ways to make amount $W$.

Recursion (min coins). Define $f(w)$ as the minimum coins needed for amount $w$.

$$f(w) = \min_{c_i \leq w} \{1 + f(w - c_i)\}$$

with $f(0) = 0$. Answer: $f(W)$.

Recursion (count ways). Define $g(i, w)$ as the number of ways using the first $i$ coin types.

$$g(i, w) = g(i-1, w) + g(i, w - c_i)$$

with $g(i, 0) = 1$ and $g(0, w) = 0$ for $w > 0$. Answer: $g(n, W)$. Complexity: $O(nW)$.

Subset Sum

Problem. Given integers $a_1, \ldots, a_n$ and a target $T$, decide whether there exists a subset $S \subseteq \{1, \ldots, n\}$ such that $\sum_{i \in S} a_i = T$.

Recursion. Define $f(i, t)$ as true if the target $t$ is achievable using the first $i$ items.

$$f(i, t) = \begin{cases} \trueval & \text{if } t = 0, \\ \falseval & \text{if } i = 0 \text{ and } t > 0, \\ f(i-1, t) \OR f(i-1, t - a_i) & \text{otherwise.} \end{cases}$$

Answer: $f(n, T)$. Complexity: $O(nT)$.

3-Partition

Problem. Given integers $a_1, \ldots, a_n$, determine whether $\{1, \ldots, n\}$ can be partitioned into three disjoint subsets $I, J, K$ such that

$$\sum_{i \in I} a_i = \sum_{j \in J} a_j = \sum_{k \in K} a_k = \frac{1}{3}\sum_{i=1}^n a_i.$$

Recursion. Let $S = \sum a_i$. If $3 \nmid S$, the answer is $\falseval$.

Define $f(i, p, q)$ as $\trueval$ if we can find disjoint $I, J \subseteq \{1, \ldots, i\}$ with $\sum_{I} a = p$ and $\sum_{J} a = q$.

$$f(i, p, q) = \begin{cases} \trueval & \text{if } i = p = q = 0, \\ \falseval & \text{if } i = 0, \\ f(i\!-\!1,\, p - a_i,\, q) \OR f(i\!-\!1,\, p,\, q - a_i) \OR f(i\!-\!1,\, p,\, q) & \text{otherwise.} \end{cases}$$

Answer: $f(n, S/3, S/3)$. Complexity: $O(n \cdot (S/3)^2)$.

Longest Increasing Subsequence

Problem. Given a sequence $a_1, \ldots, a_n$, find the length of the longest strictly increasing subsequence.

Recursion. Define $f(i)$ as the length of the LIS ending at position $i$.

$$f(i) = 1 + \max_{\substack{j < i \\ a_j < a_i}} f(j)$$

with $f(i) = 1$ if no such $j$ exists. Answer: $\max_i f(i)$.

The naive DP is $O(n^2)$. The patience sort approach achieves $O(n \log n)$: maintain an array $\mathsf{tails}$ where $\mathsf{tails}[k]$ is the smallest tail of any increasing subsequence of length $k+1$; for each $a_i$, binary search for its position.

Longest Common Subsequence

Problem. Given two strings $a = a_1 \ldots a_n$ and $b = b_1 \ldots b_m$, find the length of their longest common subsequence.

Recursion. Define $f(i, j)$ as the LCS length of $a_1 \ldots a_i$ and $b_1 \ldots b_j$.

$$f(i, j) = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0, \\ f(i-1, j-1) + 1 & \text{if } a_i = b_j, \\ \max\{f(i-1, j),\ f(i, j-1)\} & \text{otherwise.} \end{cases}$$

Answer: $f(n, m)$. Complexity: $O(nm)$.

Edit Distance

Problem. Given two strings $x = x_1 \ldots x_n$ and $y = y_1 \ldots y_m$, the edit distance (Levenshtein distance) is the minimum number of insertions, deletions, and substitutions to transform $x$ into $y$. Operations may have costs $w_{\mathrm{ins}}$, $w_{\mathrm{del}}$, and $w_{\mathrm{sub}}$.

Recursion. Define $f(i, j)$ as the minimum cost to transform $x_1 \ldots x_i$ into $y_1 \ldots y_j$.

$$f(i, j) = \begin{cases} \sum_{k=1}^{i} w_{\mathrm{del}}(x_k) & \text{if } j = 0, \\ \sum_{k=1}^{j} w_{\mathrm{ins}}(y_k) & \text{if } i = 0, \\ f(i\!-\!1, j\!-\!1) & \text{if } x_i = y_j, \\ \min \begin{cases} f(i\!-\!1, j\!-\!1) + w_{\mathrm{sub}}(x_i, y_j) \\ f(i\!-\!1, j) + w_{\mathrm{del}}(x_i) \\ f(i, j\!-\!1) + w_{\mathrm{ins}}(y_j) \end{cases} & \text{otherwise.} \end{cases}$$

Answer: $f(n, m)$. Complexity: $O(nm)$.

For unit costs ($w = 1$ for all operations):

$$f(i, j) = \begin{cases} i & \text{if } j = 0, \\ j & \text{if } i = 0, \\ f(i\!-\!1, j\!-\!1) & \text{if } x_i = y_j, \\ 1 + \min\{f(i\!-\!1, j\!-\!1),\ f(i\!-\!1, j),\ f(i, j\!-\!1)\} & \text{otherwise.} \end{cases}$$

Sequence Alignment

Problem. Find the highest-scoring alignment of two strings $x$ and $y$ based on a scoring matrix $\delta$ over the alphabet plus a gap character -. Each column of the alignment must contain a character from at least one string, and characters must appear in order.

Recursion. Define $f(i, j)$ as the maximum alignment score for suffixes $x_i \ldots x_n$ and $y_j \ldots y_m$.

$$f(i, j) = \begin{cases} 0 & \text{if } i > n \AND j > m, \\ \max \begin{cases} \delta(x_i, y_j) + f(i\!+\!1, j\!+\!1) & \text{if } i \leq n \AND j \leq m, \\ \delta(x_i, \mathtt{-}) + f(i\!+\!1, j) & \text{if } i \leq n, \\ \delta(\mathtt{-}, y_j) + f(i, j\!+\!1) & \text{if } j \leq m \end{cases} & \text{otherwise.} \end{cases}$$

Answer: $f(1, 1)$. Complexity: $O(nm)$.

Maximum Subarray

Problem. Given a sequence $s_1, s_2, \ldots, s_n$ of integers, find a contiguous subsequence with maximum sum. Also known as Kadane's algorithm.

Recursion. Define $f(i)$ as the maximum sum of a contiguous subsequence ending at position $i$.

$$f(i) = \begin{cases} s_1 & \text{if } i = 1, \\ \max\{f(i-1) + s_i,\ s_i\} & \text{otherwise.} \end{cases}$$

Answer: $\max_{1 \leq i \leq n} f(i)$. Complexity: $O(n)$.

Matrix Chain Multiplication

Problem. Given matrices $A_1, A_2, \ldots, A_n$ with dimensions $p_0 \times p_1, p_1 \times p_2, \ldots, p_{n-1} \times p_n$, find the parenthesization that minimizes the total number of scalar multiplications.

Recursion. Define $f(i, j)$ as the minimum cost to multiply $A_i \cdots A_j$.

$$f(i, j) = \begin{cases} 0 & \text{if } i = j, \\ \displaystyle\min_{i \leq k < j} \{f(i, k) + f(k\!+\!1, j) + p_{i-1} \cdot p_k \cdot p_j\} & \text{otherwise.} \end{cases}$$

Answer: $f(1, n)$. Complexity: $O(n^3)$.

With Knuth's optimization (when the optimal split is monotone), this reduces to $O(n^2)$.

Burst Balloons

Problem. Given $n$ balloons with values $a_1, \ldots, a_n$, bursting balloon $k$ earns $a_{k-1} \cdot a_k \cdot a_{k+1}$ coins (with $a_0 = a_{n+1} = 1$). Find the order that maximizes total coins.

Recursion. Define $f(l, r)$ as the maximum coins from bursting all balloons strictly between $l$ and $r$ (where $l, r$ are boundaries that remain).

$$f(l, r) = \max_{l < k < r} \{f(l, k) + f(k, r) + a_l \cdot a_k \cdot a_r\}$$

with $f(l, r) = 0$ if $r - l \leq 1$. Answer: $f(0, n\!+\!1)$. Complexity: $O(n^3)$.

Palindrome Partitioning

Problem. Given a string $s$ of length $n$, find the minimum number of cuts to partition $s$ into palindromes.

Recursion. Define $f(i)$ as the minimum cuts for $s_1 \ldots s_i$.

$$f(i) = \begin{cases} 0 & \text{if } s_1 \ldots s_i \text{ is a palindrome,} \\ \displaystyle\min_{\substack{1 \leq j < i \\ s_{j+1}\ldots s_i \text{ palindrome}}} \{f(j) + 1\} & \text{otherwise.} \end{cases}$$

Answer: $f(n)$. Precompute palindrome checks with a separate DP. Complexity: $O(n^2)$.

Rod Cutting

Problem. Given a rod of length $n$ and prices $p_1, \ldots, p_n$ where $p_i$ is the price for a piece of length $i$, find the maximum revenue from cutting and selling the rod.

Recursion. Define $f(l)$ as the maximum revenue for a rod of length $l$.

$$f(l) = \max_{1 \leq i \leq l} \{p_i + f(l - i)\}$$

with $f(0) = 0$. Answer: $f(n)$. Complexity: $O(n^2)$.

This is equivalent to the unbounded knapsack with items of weight $i$ and value $p_i$.

Travelling Salesman Problem

Problem. Given $n$ cities and pairwise distances $d[i][j]$, find the minimum-cost tour that visits every city exactly once and returns to the start.

Recursion (bitmask DP). Define $f(\mathrm{mask}, i)$ as the minimum cost to visit exactly the cities in $\mathrm{mask}$, ending at city $i$.

$$f(\mathrm{mask} \mid (1 \ll j),\ j) = \min_{i \in \mathrm{mask}} \{f(\mathrm{mask}, i) + d[i][j]\}$$

Base: $f(1 \ll 0,\ 0) = 0$. Answer: $\min_i \{f(2^n - 1, i) + d[i][0]\}$.

Complexity: $O(2^n \cdot n^2)$.

Max Independent Set on Tree

Problem. Given a tree with $n$ nodes (each with weight $w_v$), find a subset of non-adjacent nodes with maximum total weight.

Recursion. Root the tree. Define:

  • $f(v, 0)$: best value in the subtree of $v$ when $v$ is excluded.
  • $f(v, 1)$: best value when $v$ is included.

$$f(v, 0) = \sum_{u \in \mathrm{children}(v)} \max\{f(u, 0),\, f(u, 1)\}$$

$$f(v, 1) = w_v + \sum_{u \in \mathrm{children}(v)} f(u, 0)$$

Answer: $\max\{f(\mathrm{root}, 0),\, f(\mathrm{root}, 1)\}$. Complexity: $O(n)$.

Tree Diameter

Problem. Find the longest path (in edges or weights) between any two nodes in a tree.

Recursion. Root the tree. Define $f(v)$ as the length of the longest path going downward from $v$.

$$f(v) = \max_{u \in \mathrm{children}(v)} \{1 + f(u)\}$$

with $f(\mathrm{leaf}) = 0$. The diameter is updated at each node as the sum of the two longest child paths:

$$\mathrm{diameter} = \max_v \{f_1(v) + f_2(v)\}$$

where $f_1, f_2$ are the two largest values of $1 + f(u)$ among children of $v$. Complexity: $O(n)$.

Digit DP

Problem. Count integers in $[0, N]$ satisfying constraints on their digits (e.g., digit sum equals $S$, no adjacent equal digits, divisibility).

Recursion. State: $(\mathrm{pos},\, \mathrm{tight},\, \ldots)$ where $\mathrm{tight}$ tracks whether the prefix so far equals the prefix of $N$.

$$f(\mathrm{pos}, \mathrm{tight}, \ldots) = \sum_{d=0}^{\mathrm{limit}} f(\mathrm{pos}+1,\ \mathrm{tight} \AND (d = \mathrm{limit}),\ \ldots)$$

where $\mathrm{limit} = N[\mathrm{pos}]$ if $\mathrm{tight}$, else $9$.

For range $[L, R]$: compute $f(R) - f(L-1)$.

DP on DAG

Problem. Find the longest (or shortest) path, or count paths, in a directed acyclic graph.

Recursion. Process vertices in topological order.

Longest path: $$f(v) = \max_{u \to v} \{f(u) + w(u, v)\}$$

Path count: $$\mathrm{cnt}(v) = \sum_{u \to v} \mathrm{cnt}(u)$$

Many DP problems can be modeled as DAG problems: whenever states form a DAG, think topological sort.

Expected Value DP

Problem. Compute the expected cost or number of steps to reach a terminal state from a given starting state, where transitions are probabilistic.

Recursion.

$$E[s] = \sum_{s'} p(s \to s') \cdot (c(s, s') + E[s'])$$

where $p(s \to s')$ is the transition probability and $c(s, s')$ is the transition cost.

Key property: linearity of expectation — $E[X_1 + \cdots + X_n] = \sum E[X_i]$, even when the $X_i$ are dependent.

Work backwards from terminal states. If absorbing states exist, set up equations and solve.

Game Theory DP

Problem. Two players alternate moves in an impartial game. Determine who wins with optimal play.

Recursion (Sprague-Grundy). Every impartial game position $s$ has a Grundy value:

$$\mathrm{SG}(s) = \mathrm{mex}\big(\{\mathrm{SG}(s') : s \to s'\}\big)$$

where $\mathrm{mex}$ is the minimum excludant (smallest non-negative integer not in the set).

A position is losing iff $\mathrm{SG}(s) = 0$.

Nim: $n$ piles of sizes $a_1, \ldots, a_n$. First player wins iff $a_1 \oplus a_2 \oplus \cdots \oplus a_n \neq 0$.

Composite games: $\mathrm{SG} = \mathrm{SG}_1 \oplus \mathrm{SG}_2 \oplus \cdots$ (XOR of independent subgames).

Originally created October 2018 at the University of Bergen. Expanded April 2026.