Abstracting a Tabular DP algorithm

The Trigger

The formal definition of how a tabular DP algorithm operates is clear enough, but what if there is a visual way to quickly abstract it?

---

Coin-Collecting

Formal Definition

$$F(i,j)=\max \{F(i-1),F(i,j-1)\}+c_{ij}$$

Visual Abstraction

Binomial Coefficient

Formal Definition

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=|\begin{array}{ll}1& \text{ if }k=0\text{ or }n=k\\ \left(\genfrac{}{}{0ex}{}{n-1}{k}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)& \text{o.w.}\end{array}$$

Visual Abstraction

Longest Common Subsequence

Formal Definition

$$\text{len}(i,j)=|\begin{array}{ll}\text{len}(i-1,j-1)+1& \text{if }{a}_i=b_j\\ \max \{\text{len}(i,j-1),\text{len}(i-1,j)\}& \text{ if }{a}_i\ne b_j\\ 0& \text{ if }i=0\text{ or }j=0\end{array}$$

Visual Abstraction

Coin-Row

Formal Definition

$$F(n)=|\begin{array}{ll}\max \{F(n-1),F(n-2)+c_n\}& \text{ if }n>1\\ 0& \text{ if }n=0\\ c_1& \text{ if }n=1\end{array}$$

Visual Abstraction

0/1 Knapsack

Formal Definition

$$V[i,j]=|\begin{array}{ll}V[i-1,j]& \text{ if }j-w_i<0\\ \max \{V[i-1,j],V[i-1,j-w_i]+v_i\}& \text{ if }j-w_i\ge 0\end{array}$$

Visual Abstraction

---

Connections