Dynamic Programming
Contents
Introduction
What is dynamic programming (DP)?
- DP is an algorithm design technique
- DP can be better renamed as store-and-conquer
- DP finds optimal solutions to a problem by combining optimal solutions to its overlapping subproblems by saving solutions to subproblems in a table and never recomputing them
- DP is a table filling method where the value at each cell (solution to a subproblem) depends on the values at two or more other cells (solutions to overlapping subproblems)
Recurrence leads to recursive/DP algorithms
- Recurrence is the brain of dynamic programming.
- Once we have a recurrence, it is relatively easy to derive a recursive or top-down DP or bottom-up DP algorithm.
- Bottom-up DP is typically the fastest in practice.
| Feature | Recursive | Top-down DP | Bottom-up DP |
|---|---|---|---|
| Uses | Recursion | Memoization | Tabulation |
| Each subproblem computed | $\ge 1$ time | $\le 1$ time | $= 1$ time |
| Computation graph | Tree | DAG | DAG |
| Coding | Very easy | Easy | Okay |
| Complexity | Exponential | Polynomial | Polynomial |
Problem-Solving Template
Problems and Solutions
Sanskrit Poetry
Problem
In classic Sanskrit poetry, in one category of poetic meters, each line
of a poem consists of a fixed number of beats (or time units). There are
two types of syllables:
Given a natural number $n$, in how many ways can one create an $n$-beat poetry line consisting of short and long syllables?
- short, denoted by $\square$, which takes $1$ beat
- long, denoted by $\sqsubset \sqsupset$, which takes $2$ beats
Given a natural number $n$, in how many ways can one create an $n$-beat poetry line consisting of short and long syllables?
The solution to this problem is the first known DP logic in literature. The recurrence is discovered by Pingala in the second half of 1st millenium BCE and published in the book ChandahSuthra. The book is on combinatorics and gives several recursive algorithms for computing power (or exponentiation), binomial coefficients, permutation generation, and converting binary to decimal.
Step 1. Subproblem
\[ \begin{align*} &S[i] = \text{Count ways to create an $i$-beats line using $\square$ and $\sqsubset \sqsupset$ such that}\\ &\qquad\qquad \text{$\square$ occupies the last position.}\\ &L[i] = \text{Count ways to create an $i$-beats line using $\square$ and $\sqsubset \sqsupset$ such that}\\ &\qquad\qquad \text{$\sqsubset \sqsupset$ occupies the last position.}\\ &\text{Compute $(S[n] + L[n]).$} \end{align*} \]Step 2. Recurrence
For all $i \in [1, n]$,
\[ \begin{aligned} &S[i] = \left. \begin{cases} 1 & \text{if } i \le 2,\\ S[i - 1] + L[i - 1] & \text{if } i > 2. \end{cases} \right\}\\ &L[i] = \left. \begin{cases} (i - 1) & \text{if } i \le 2,\\ S[i - 2] + L[i - 2] & \text{if } i > 2. \end{cases} \right\} \end{aligned} \]![Recurrence diagram for S[i] depending on S[i-1] and L[i-1]](images/dynamicprogramming-sanskrit-recurrence.svg)
Step 3. Dependency
Step 4. Algorithm
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{BottomUp}{$n$}
\STATE Create arrays $S[1 \ldots \max(2, n)]$ and $L[1 \ldots \max(2, n)]$
\STATE $S[1] \gets 1$; $S[2] \gets 1$
\STATE $L[1] \gets 0$; $L[2] \gets 1$
\FOR{$i \gets 3$ \TO $n$}
\STATE $S[i] \gets S[i - 1] + L[i - 1]$
\STATE $L[i] \gets S[i - 2] + L[i - 2]$
\ENDFOR
\RETURN $(S[n] + L[n])$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Step 5. Table
| $i$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | $15$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $S[i]$ | $1$ | $1$ | $2$ | $3$ | $5$ | $8$ | $13$ | $21$ | $34$ | $55$ | $89$ | $144$ | $233$ | $377$ | $610$ |
| $L[i]$ | $0$ | $1$ | $1$ | $2$ | $3$ | $5$ | $8$ | $13$ | $21$ | $34$ | $55$ | $89$ | $144$ | $233$ | $377$ |
Step 6. Complexity
Time $\asymp n$. Space $\asymp n$.
Step 7. Extensions
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{SpaceOptimized}{$n$} \COMMENT{Time $\asymp n$, Space $\asymp 1$}
\STATE $sprev \gets 0$; $scurr \gets 1$
\STATE $\ell prev \gets 1$; $\ell curr \gets 0$
\FOR{$i \gets 2$ \TO $n$}
\STATE $snext \gets scurr + \ell curr$
\STATE $\ell next \gets sprev + \ell prev$
\STATE $sprev \gets scurr$
\STATE $scurr \gets snext$
\STATE $\ell prev \gets \ell curr$
\STATE $\ell curr \gets \ell next$
\ENDFOR
\RETURN $(scurr + \ell curr)$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Better Solution
Step 1. Subproblem
\[ \begin{aligned} &C[i] = \text{Count ways to create an $i$-beats line using $\square$ and $\sqsubset \sqsupset$.}\\ &\text{Compute $C[n].$} \end{aligned} \]Step 2. Recurrence
For all $i \in [1, n]$,
\[ C[i] = \left. \begin{cases} i & \text{if } i \le 2,\\ C[i - 1] + C[i - 2] & \text{if } i > 2. \end{cases} \right\} \]![Recurrence diagram for C[i] depending on C[i-1] and C[i-2]](images/dp-sanskrit-recurrence2.svg)
Step 3. Dependency
Step 4. Algorithm
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{BottomUp}{$n$}
\STATE Create an array $C[1 \ldots \max(2, n)]$
\STATE $C[1] \gets 1$; $C[2] \gets 2$
\FOR{$i \gets 3$ \TO $n$}
\STATE $C[i] \gets C[i - 1] + C[i - 2]$
\ENDFOR
\RETURN $C[n]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Step 5. Table
| $i$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | $15$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $C[i]$ | $1$ | $2$ | $3$ | $5$ | $8$ | $13$ | $21$ | $34$ | $55$ | $89$ | $144$ | $233$ | $377$ | $610$ | $987$ |
Step 6. Complexity
Time $\asymp n$. Space $\asymp n$.
Step 7. Extensions
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{SpaceOptimized}{$n$} \COMMENT{Time $\asymp n$, Space $\asymp 1$}
\STATE $prev \gets 1$; $curr \gets 1$
\FOR{$i \gets 2$ \TO $n$}
\STATE $next \gets curr + prev$
\STATE $prev \gets curr$
\STATE $curr \gets next$
\ENDFOR
\RETURN $curr$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Binomial Coefficient
Problem
Given a natural number $n$ and a whole number $r \in [0, n]$, compute
$^nC_r$ or $\binom{n}{r}$, where, $^nC_r = \frac{n!}{r!(n-r)!}$ and
denotes the number of ways to choose $r$ elements from a set of $n$
elements. These numbers are called binomial coefficients because they
are the coefficients of the binomial theorem $(x + y)^n = \sum_{r=0}^{n}
{^n}C_r x^{n-r} y^r$.
Step 1. Subproblem
\[ \begin{aligned} &C[i][j] = {^i}C_j, \text{ where } 0 \le j \le i.\\ &\text{Compute $C[n][r]$.} \end{aligned} \]Step 2. Recurrence
For all $i \in [0, n]$, $j \in [0, n]$,
\[ C[i][j] = \left. \begin{cases} 0 & \text{if } j > i,\\ 1 & \text{if } j = 0 \text{ or } j = i,\\ C[i - 1][j - 1] + C[i - 1][j] & \text{if } j \in [1, (i-1)]. \end{cases} \right\} \]![Recurrence diagram for C[i][j] depending on C[i-1][j-1] and C[i-1][j]](images/dp-binomial-recurrence.svg)
Step 3. Dependency
Step 4. Algorithm
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{BottomUp}{$n, r$}
\STATE Create a $2$-D array $C[0 \ldots n][0 \ldots r]$
\STATE $C[0 \ldots n][0] \gets [1 \ldots 1]$
\FOR{$i \gets 1$ \TO $n$}
\FOR{$j \gets 1$ \TO $\min(i, r)$}
\STATE $C[i][j] \gets C[i - 1][j - 1] + (~ j < i ~?~ C[i - 1][j] ~:~ 0 ~)$
\ENDFOR
\ENDFOR
\RETURN $C[n][r]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Step 5. Table
| $C[i][j]$ | $j=0$ | $j=1$ | $j=2$ | $j=3$ |
|---|---|---|---|---|
| $i=0$ | $1$ | $0$ | $0$ | $0$ |
| $i=1$ | $1$ | $1$ | $0$ | $0$ |
| $i=2$ | $1$ | $2$ | $1$ | $0$ |
| $i=3$ | $1$ | $3$ | $3$ | $1$ |
| $i=4$ | $1$ | $4$ | $6$ | $4$ |
Step 6. Complexity
Time $\asymp n \cdot \min(n, r)$. Space $\asymp n \cdot \min(n, r)$.
Step 7. Extensions
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{SpaceOptimized}{$n, r$} \COMMENT{Time $\asymp n \cdot \min(n, r)$, Space $\asymp \min(n, r)$}
\STATE Create arrays $curr[0 \ldots r]$ and $next[0 \ldots r]$
\STATE $curr[0] \gets 1$; $next[0] \gets 1$
\FOR{$i \gets 1$ \TO $n$}
\FOR{$j \gets 1$ \TO $\min(i, r)$}
\STATE $next[j] \gets curr[j - 1] + (~ j < i ~?~ curr[j] ~:~ 0 ~)$
\ENDFOR
\STATE $\text{swap}(curr, next)$
\ENDFOR
\RETURN $curr[r]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Longest Common Subsequence
Problem
Given two strings $x[1 \ldots m]$ and $y[1 \ldots n]$, compute the
length of the longest common subsequence (LCS) between $x$ and $y$.
Example: the LCS between strings "einstein" and "newton" are "etn",
"nen", and "ntn" and have length $3$.
Step 1. Subproblem
\[ \begin{aligned} &L[i][j] = \text{Length of the LCS between strings $x[1 \ldots i]$ and $y[1 \ldots j]$.}\\ &\text{Compute $L[m][n]$.} \end{aligned} \]Step 2. Recurrence
For all $i \in [0, m]$, $j \in [0, n]$,
\[ L[i][j] = \left. \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0,\\ \left. \begin{cases} 1 + L[i-1][j-1] & \text{if } x[i] = y[j],\\ \max \left( \begin{array}{@{}l@{}} L[i][j-1],\\ L[i-1][j] \end{array} \right) & \text{if } x[i] \ne y[j]. \end{cases} \right\} & \text{if } i > 0, j > 0. \end{cases} \right\} \]![Recurrence diagram for L[i][j] depending on L[i-1][j-1], L[i][j-1], and L[i-1][j]](images/dp-lcs-recurrence.svg)
Step 3. Dependency
Step 4. Algorithm
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{BottomUp}{$x[1 \ldots m], y[1 \ldots n]$}
\STATE Create a 2-D array $L[0 \ldots m][0 \ldots n]$
\STATE $L[0 \ldots m][0] \gets [0 \ldots 0]$; $L[0][1 \ldots n] \gets [0 \ldots 0]$
\FOR{$i \gets 1$ \TO $m$}
\FOR{$j \gets 1$ \TO $n$}
\IF{$x[i] = y[j]$}
\STATE $L[i][j] \gets 1 + L[i-1][j-1]$
\ELSE
\STATE $L[i][j] \gets \max(L[i-1][j], L[i][j-1])$
\ENDIF
\ENDFOR
\ENDFOR
\RETURN $L[m][n]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Step 5. Table
| $L[i][j]$ | $0$ | $1~(y[1]=e)$ | $2~(y[2]=i)$ | $3~(y[3]=n)$ | $4~(y[4]=s)$ | $5~(y[5]=t)$ | $6~(y[6]=e)$ | $7~(y[7]=i)$ | $8~(y[8]=n)$ |
|---|---|---|---|---|---|---|---|---|---|
| $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ |
| $1~(x[1]=n)$ | $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ |
| $2~(x[2]=e)$ | $0$ | $1$ | $1$ | $1$ | $1$ | $1$ | $2$ | $2$ | $2$ |
| $3~(x[3]=w)$ | $0$ | $1$ | $1$ | $1$ | $1$ | $1$ | $2$ | $2$ | $2$ |
| $4~(x[4]=t)$ | $0$ | $1$ | $1$ | $1$ | $1$ | $2$ | $2$ | $2$ | $2$ |
| $5~(x[5]=o)$ | $0$ | $1$ | $1$ | $1$ | $1$ | $2$ | $2$ | $2$ | $2$ |
| $6~(x[6]=n)$ | $0$ | $1$ | $1$ | $2$ | $2$ | $2$ | $2$ | $2$ | $3$ |
Step 6. Complexity
Time $\asymp mn$. Space $\asymp mn$.
Step 7. Extensions
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{SpaceOptimized}{$x[1 \ldots m], y[1 \ldots n]$} \COMMENT{Time $\asymp mn$, Space $\asymp \min(m,n)$}
\IF{$m < n$}
\STATE $\text{swap}(x, y)$; $\text{swap}(m, n)$
\ENDIF
\STATE Create arrays $curr[0 \ldots n] \gets [0 \ldots 0]$, $next[0 \ldots n] \gets [0 \ldots 0]$
\FOR{$i \gets 1$ \TO $m$}
\FOR{$j \gets 1$ \TO $n$}
\IF{$x[i] = y[j]$}
\STATE $next[j] \gets 1 + curr[j-1]$
\ELSE
\STATE $next[j] \gets \max(curr[j], next[j-1])$
\ENDIF
\ENDFOR
\STATE $\text{swap}(curr, next)$
\ENDFOR
\RETURN $curr[n]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{GetSolution}{$x[1 \ldots m], y[1 \ldots n]$} \COMMENT{Time $\asymp mn$, Space $\asymp mn$}
\STATE // Forward Phase
\STATE Construct $L[0 \ldots m][0 \ldots n]$ using code from BottomUp
\STATE // Backward Phase
\STATE Create an empty string $lcs[1 \ldots L[m][n]]$
\STATE $i \gets m$; $j \gets n$; $k \gets L[m][n]$
\WHILE{$k > 0$}
\IF{$x[i] = y[j]$}
\STATE $lcs[k] \gets x[i]$
\STATE $i \gets i-1$
\STATE $j \gets j-1$
\STATE $k \gets k-1$
\ELSIF{$L[i-1][j] > L[i][j-1]$}
\STATE $i \gets i-1$
\ELSE
\STATE $j \gets j-1$
\ENDIF
\ENDWHILE
\RETURN $\langle L[m][n], lcs[1 \ldots L[m][n]] \rangle$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Edit Distance
Problem
Given two strings $x[1 \ldots m]$ and $y[1 \ldots n]$, compute the
minimum number of edits required to convert string $x$ into string $y$.
For converting a string, we can use any of the three edit operations:
insert, delete, and replace.
Example: minimum edits required to convert "newton" to "einstein" is $6$:
\[ \begin{aligned} &\text{newton} \xrightarrow{\text{ins}} \text{newtoin} \xrightarrow{\text{rep}} \text{newtein} \xrightarrow{\text{ins}} \text{newstein} \xrightarrow{\text{ins}} \text{newnstein} \xrightarrow{\text{rep}} \text{neinstein} \xrightarrow{\text{del}} \text{einstein} \end{aligned} \]Step 1. Subproblem
\[ \begin{aligned} &D[i][j] = \text{Least editing distance between strings $x[1 \ldots i]$ and $y[1 \ldots j]$.}\\ &\text{Compute $D[m][n]$.} \end{aligned} \]Step 2. Recurrence
For all $i \in [0, m]$, $j \in [0, n]$,
\[ D[i][j] = \left. \begin{cases} i & \text{if } j = 0,\\ j & \text{if } i = 0,\\ \left. \begin{cases} D[i-1][j-1] & \text{if } x[i] = y[j],\\ 1 + \min \left( \begin{array}{@{}l@{}} D[i-1][j],\\ D[i][j-1],\\ D[i-1][j-1] \end{array} \right) & \text{if } x[i] \ne y[j]. \end{cases} \right\} & \text{if } i > 0, j > 0. \end{cases} \right\} \]![Recurrence diagram for D[i][j] depending on D[i-1][j-1], D[i-1][j], D[i][j-1]](images/dp-editdistance-recurrence.svg)
Step 3. Dependency
Step 4. Algorithm
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{BottomUp}{$x[1 \ldots m], y[1 \ldots n]$}
\STATE Create a 2-D array $D[0 \ldots m][0 \ldots n]$
\STATE $D[0 \ldots m][0] \gets [0 \ldots m]$ \COMMENT{initialize $0$th column}
\STATE $D[0][1 \ldots n] \gets [1 \ldots n]$ \COMMENT{initialize $0$th row}
\FOR{$i \gets 1$ \TO $m$}
\FOR{$j \gets 1$ \TO $n$}
\IF{$x[i] = y[j]$}
\STATE $noedit \gets D[i-1][j-1]$
\STATE $D[i][j] \gets noedit$
\ELSE
\STATE $delete \gets D[i-1][j] + 1$
\STATE $insert \gets D[i][j-1] + 1$
\STATE $replace \gets D[i-1][j-1] + 1$
\STATE $D[i][j] \gets \min(delete, insert, replace)$
\ENDIF
\ENDFOR
\ENDFOR
\RETURN $D[m][n]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Step 5. Table
| $D[i][j]$ | $0$ | $1~(y[1]=e)$ | $2~(y[2]=i)$ | $3~(y[3]=n)$ | $4~(y[4]=s)$ | $5~(y[5]=t)$ | $6~(y[6]=e)$ | $7~(y[7]=i)$ | $8~(y[8]=n)$ |
|---|---|---|---|---|---|---|---|---|---|
| $0$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ |
| $1~(x[1]=n)$ | $1$ | $1$ | $2$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
| $2~(x[2]=e)$ | $2$ | $1$ | $2$ | $3$ | $3$ | $4$ | $4$ | $5$ | $6$ |
| $3~(x[3]=w)$ | $3$ | $2$ | $2$ | $3$ | $4$ | $4$ | $5$ | $5$ | $6$ |
| $4~(x[4]=t)$ | $4$ | $3$ | $3$ | $3$ | $4$ | $4$ | $5$ | $6$ | $6$ |
| $5~(x[5]=o)$ | $5$ | $4$ | $4$ | $4$ | $4$ | $5$ | $5$ | $6$ | $7$ |
| $6~(x[6]=n)$ | $6$ | $5$ | $5$ | $4$ | $5$ | $5$ | $6$ | $6$ | $6$ |
Step 6. Complexity
Time $\asymp mn$. Space $\asymp mn$.
Step 7. Extensions
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{SpaceOptimized}{$x[1 \ldots m], y[1 \ldots n]$} \COMMENT{Time $\asymp mn$, Space $\asymp \min(m,n)$}
\IF{$m < n$}
\STATE $\text{swap}(x, y)$; $\text{swap}(m, n)$
\ENDIF
\STATE Create arrays $curr[0 \ldots n] \gets [0 \ldots 0]$, $next[0 \ldots n] \gets [0 \ldots 0]$
\FOR{$i \gets 1$ \TO $m$}
\FOR{$j \gets 1$ \TO $n$}
\IF{$x[i] = y[j]$}
\STATE $next[j] \gets 1 + curr[j-1]$
\ELSE
\STATE $next[j] \gets 1 + \max(curr[j], curr[j-1], next[j-1])$
\ENDIF
\ENDFOR
\STATE $\text{swap}(curr, next)$
\ENDFOR
\RETURN $curr[n]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{GetSolution}{$x[1 \ldots m], y[1 \ldots n]$} \Comment {Time $\asymp mn$, Space $\asymp mn$}
\STATE // Forward Phase
\STATE Construct $D[0 \ldots m][0 \ldots n]$ using code from BottomUp
\STATE // Backward Phase
\STATE Create an array $edits[1 \ldots D[m][n]]$
\STATE $i \gets m$; $j \gets n$; $k \gets 1$
\WHILE{$i > 1$ \AND $j > 1$}
\IF{$x[i] = y[j]$}
\STATE $i \gets i-1$; $j \gets j-1$
\ELSIF{$D[i-1][j-1] < D[i-1][j]$ \AND $D[i-1][j-1] < D[i][j-1]$}
\STATE $edits[k] \gets$ ``Replace $x[i]$ with $y[j]$ at index $i$"
\STATE $i \gets i-1$; $j \gets j-1$; $k \gets k+1$
\ELSIF{$D[i-1][j] < D[i][j-1]$}
\STATE $edits[k] \gets$ ``Delete $x[i]$ at index $i$"
\STATE $i \gets i-1$; $k \gets k+1$
\ELSE
\STATE $edits[k] \gets$ ``Insert $y[j]$ after index $i$"
\STATE $j \gets j-1$; $k \gets k+1$
\ENDIF
\ENDWHILE
\WHILE{$i > 1$}
\STATE $edits[k] \gets$ ``Delete $x[i]$ at index $i$"
\STATE $i \gets i-1$; $k \gets k+1$
\ENDWHILE
\WHILE{$j > 1$}
\STATE $edits[k] \gets$ ``Insert $y[j]$ after index $i$"
\STATE $j \gets j-1$; $k \gets k+1$
\ENDWHILE
\RETURN $\langle D[m][n], edits \rangle$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Knapsack
Problem
Given a set of $n$ items numbered from 1 to $n$ such that item $i$ has
weight $w[i]$ and value $v[i]$, find the maximum total value of the
items that can fit in a knapsack with the maximum weight capacity of
natural number $W$. That is, compute the maximum value of
$\sum_{i=1}^{n} x[i] \cdot v[i]$ subject to the constraints
$\sum_{i=1}^{n} x[i] \cdot w[i] \le W$ and $x[i] \in \{0, 1\}$. Assume
that $W \geq \min(w[1 \ldots n])$. If not, there is no solution.
Example: When $n = 5$, $w[1 \ldots 5] = [2,3,7,9,15]$, $v[1 \ldots 5] = [10,15,25,13,55]$, $W = 12$, then maximum total value $= 50$ for the solution set $\{1,2,3\}$.
Step 1. Subproblem
\[ \begin{aligned} &K[i][j] = \text{Max total value the knapsack can hold for the first $i$ items}\\ &\text{with capacity at most $j$, assuming an item is considered at most once.}\\ &\text{Compute $K[n][W]$.} \end{aligned} \]Step 2. Recurrence
For all $i \in [0, n]$, $j \in [0, W]$,
\[ K[i][j] = \left. \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0,\\ \max \left\{ \begin{array}{@{}l@{}} K[i-1][j],\\ (K[i-1][j-w[i]] + v[i]) \times [j \ge w[i]] \end{array} \right\} & \text{if } i > 0, j > 0. \end{cases} \right\} \]![Recurrence diagram for K[i][j] depending on K[i-1][j] and K[i-1][j-w[i]]+v[i]](images/dp-knapsack-recurrence.svg)
Step 3. Dependency
Step 4. Algorithm
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{BottomUp}{$v[1 \ldots n], w[1 \ldots n], W$}
\STATE Create a 2-D array $K[0 \ldots n][0 \ldots W]$
\STATE $K[0 \ldots n][0] \gets [0 \ldots 0]$ \COMMENT{initialize $0$th column}
\STATE $K[0][1 \ldots W] \gets [0 \ldots 0]$ \COMMENT{initialize $0$th row}
\FOR{$i \gets 1$ \TO $n$}
\FOR{$j \gets 1$ \TO $W$}
\STATE $excludeitem \gets K[i-1][j]$
\STATE $includeitem \gets (~ j \ge w[i] ~?~ K[i-1][j-w[i]] + v[i] ~:~ 0 ~)$
\STATE $K[i][j] \gets \max(excludeitem, includeitem)$
\ENDFOR
\ENDFOR
\RETURN $K[n][W]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Step 5. Table
$W = 12$
| $i$ | $v[i]$ | $w[i]$ |
|---|---|---|
| $0$ | $-$ | $-$ |
| $1$ | $10$ | $2$ |
| $2$ | $15$ | $3$ |
| $3$ | $25$ | $7$ |
| $K[i][j]$ | $j=0$ | $j=1$ | $j=2$ | $j=3$ | $j=4$ | $j=5$ | $j=6$ | $j=7$ | $j=8$ | $j=9$ | $j=10$ | $j=11$ | $j=12$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $i=0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ |
| $i=1$ | $0$ | $0$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ |
| $i=2$ | $0$ | $0$ | $10$ | $15$ | $15$ | $25$ | $25$ | $25$ | $25$ | $25$ | $25$ | $25$ | $25$ |
| $i=3$ | $0$ | $0$ | $10$ | $15$ | $15$ | $25$ | $25$ | $25$ | $25$ | $35$ | $40$ | $40$ | $50$ |
Step 6. Complexity
Time $\asymp nW$. Space $\asymp nW$.
Step 7. Extensions
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{SpaceOptimized}{$v[1 \ldots n], w[1 \ldots n], W$} \COMMENT{Time $\asymp nW$, Space $\asymp W$}
\STATE Create arrays $curr[0 \ldots W]$ and $next[0 \ldots W]$
\STATE $curr[0] \gets 0$; $next[0] \gets 0$
\FOR{$i \gets 1$ \TO $n$}
\FOR{$j \gets 1$ \TO $W$}
\STATE $next[j] \gets \max(curr[j],\ (~ j \ge w[i] ~?~ curr[j-w[i]] + v[i] ~:~ 0 ~))$
\ENDFOR
\STATE $\text{swap}(curr, next)$
\ENDFOR
\RETURN $curr[W]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{GetSolution}{$v[1 \ldots n], w[1 \ldots n], W$} \COMMENT{Time $\asymp nW$, Space $\asymp nW$}
\STATE // Forward Phase
\STATE Construct $K[0 \ldots n][0 \ldots W]$ using code from BottomUp
\STATE // Backward Phase
\STATE // $frequencies[i] = x[i] =$ count of item $i$
\STATE Create an array $frequencies[0 \ldots n] \gets [0 \ldots 0]$
\STATE $i \gets n$; $j \gets W$
\WHILE{$i > 0$ \AND $j > 0$}
\IF{$K[i][j] \neq K[i-1][j]$}
\STATE $frequencies[i] \gets frequencies[i] + 1$
\STATE $j \gets j - w[i]$
\ENDIF
\STATE $i \gets i-1$
\ENDWHILE
\RETURN $\langle K[n][W], frequencies[1 \ldots n] \rangle$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Matrix-Chain Multiplication
Problem
Given a chain of $n$ matrices $a_1, a_2, \ldots, a_n$ such that matrix
$a_i$ has dimension $p[i-1] \times p[i]$, design an algorithm to
parenthesize the matrix-chain product $a_1 \times a_2 \times \cdots
\times a_n$ that minimizes the number of multiplications.
Step 1. Subproblem
\[ \begin{aligned} &M[i][j] = \text{Minimum \#multiplications needed to compute the}\\ &\qquad\qquad\qquad \text{matrix-chain product $a_i \times a_{i+1} \times \cdots \times a_j$, where,}\\ &\qquad\qquad\qquad \text{the size of matrix $a_i$ is $p[i-1] \times p[i]$.}\\ &\text{Compute $M[1][n]$.} \end{aligned} \]Step 2. Recurrence
For all $1 \le i \le j \le n$,
\[ M[i][j] = \left. \begin{cases} 0 & \text{if } i = j,\\ \min\limits_{k \in [i,\, j-1]} \left( \begin{array}{l} M[i][k] + M[k+1][j] + p[i-1] \times p[k] \times p[j] \end{array} \right) & \text{if } i < j. \end{cases} \right\} \]![Recurrence diagram for M[i][j] depending on M[i][k] and M[k+1][j]](images/dp-mcm-recurrence.svg)
Step 3. Dependency
Step 4. Algorithm
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{BottomUp}{$p[0 \ldots n]$}
\STATE Create a 2-D array $M[1 \ldots n][1 \ldots n]$
\FOR{$i \gets 1$ \TO $n$}
\STATE $M[i][i] \gets 0$
\ENDFOR
\FOR{$diagonal \gets 2$ \TO $n$}
\FOR{$i \gets 1$ \TO $(n - diagonal + 1)$}
\STATE $j \gets i + diagonal - 1$
\STATE $M[i][j] \gets \infty$
\FOR{$k \gets i$ \TO $j-1$}
\STATE $M[i][j] \gets \min(M[i][j],\ M[i][k] + M[k+1][j] + p[i-1] \times p[k] \times p[j])$
\ENDFOR
\ENDFOR
\ENDFOR
\RETURN $M[1][n]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Step 5. Table
| $i$ | $0$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|---|
| $p[i]$ | $1$ | $2$ | $3$ | $4$ | $3$ |
| $M[i][j]$ | $j=1$ | $j=2$ | $j=3$ | $j=4$ |
|---|---|---|---|---|
| $i=1$ | $0$ | $6$ | $18$ | $30$ |
| $i=2$ | $-$ | $0$ | $24$ | $48$ |
| $i=3$ | $-$ | $-$ | $0$ | $36$ |
| $i=4$ | $-$ | $-$ | $-$ | $0$ |
Step 6. Complexity
Time $\asymp n^3$. Space $\asymp n^2$.
Step 7. Extensions
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{GetSolution}{$p[0 \ldots n]$} \COMMENT{Time $\asymp n^3$, Space $\asymp n^2$}
\STATE // Forward phase
\STATE Create 2-D arrays $M[1 \ldots n][1 \ldots n]$ and $P[1 \ldots n][1 \ldots n]$
\FOR{$i \gets 1$ \TO $n$}
\STATE $M[i][i] \gets 0$
\ENDFOR
\FOR{$diagonal \gets 2$ \TO $n$}
\FOR{$i \gets 1$ \TO $(n - diagonal + 1)$}
\STATE $j \gets i + diagonal - 1$
\STATE $M[i][j] \gets \infty$
\FOR{$k \gets i$ \TO $(j-1)$}
\STATE $value \gets M[i][k] + M[k+1][j] + p[i-1] \times p[k] \times p[j]$
\IF{$M[i][j] > value$}
\STATE $M[i][j] \gets value$
\STATE $P[i][j] \gets k$
\ENDIF
\ENDFOR
\ENDFOR
\ENDFOR
\STATE // Backward phase
\STATE Create a dynamic array $R$
\STATE Create a stack $S$; $S.\text{Push}(\langle 1, n, 0 \rangle)$
\WHILE{stack $S$ is not empty}
\STATE $\langle i, j, state \rangle \gets S.\text{Pop}()$
\IF{$i = j$}
\STATE $R.\text{Add}(A_i)$
\ENDIF
\IF{$state = 0$}
\STATE $R.\text{Add}(\text{``("})$
\STATE $S.\text{Push}(\langle i, j, 1 \rangle)$
\STATE $S.\text{Push}(\langle i, P[i][j], 0 \rangle)$
\ELSIF{$state = 1$}
\STATE $S.\text{Push}(\langle i, j, 2 \rangle)$
\STATE $S.\text{Push}(\langle P[i][j]+1, j, 0 \rangle)$
\ELSE
\STATE $R.\text{Add}(\text{``)"})$
\ENDIF
\ENDWHILE
\RETURN $\langle M[1][n], R \rangle$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}