Notation for Dynamic Programming Algorithms
Here we collect notation related to dyanmic programming algorithms (and the problems they solve).
Subset Sum Problem
| Notation | Meaning |
| $w_1,\dots,w_n$ | The set of all $n$ integers (assume $w_i > 0$ for every $i\in [n]$) |
| $W$ | The total bound/budget $W\ge 0$. |
| $S$ | A subset $S\subseteq [n]$, what we should output. |
| $w(S)$ | Weight of $S$, defined as $\sum_{i\in S} w_i$. Our goal is to put an $S$ that maximizes $w(S)$. |
| $\text{OPT}(j,B)$ | Weight of the optimal subset for the numbers $w_1,\dots,w_j$ and budget $B$. |
| $M$ | An $(W+1)\times (n+1)$ matrix that is computed by the algorithm such that $M[B][j]=\text{OPT}(j,B)$. |
Shortest Path Problem
| Notation | Meaning |
| $c_e$ | Given a (directed) graph $G=(V,E)$ where every edge $e\in E$ has a cost $c_e$ (which can be negative). |
| $t$ | Terminal $t\in V$. The goal is to find the shorest path from every $s\in V$ to $t$. |
| Negative cycle | A cycle $C$ such that $\sum_{e\in C} c_e < 0$. We assume $G$ has no negative cycles. |
| $\text{OPT}(u,i)$ | Cost of shortest $u-t$ path with at most $i$ edges in it. We are interested in $\text{OPT}(s,n-1)$ for every $s\in V$. |