test_reference_dptable

Sequence $a = [3, 1, 8, 2, 5, 4, 7, 6]$. Compute $dp[i]$ = length of LIS ending at index $i$.

Base case: $dp[0] = 1$. Any single element is an increasing subsequence of length 1.

$i=1$: $a[1]=1$. Check $a[0]=3 > 1$, so no valid predecessor. $dp[1] = 1$.

$dp[1] = 1$. No transition arrow needed.

$i=2$: $a[2]=8$. Both $a[0]=3$ and $a[1]=1$ are smaller. Best is $dp[0]=1$. So $dp[2] = 2$.

$dp[2] = 2$, coming from index 0.

$i=3$: $a[3]=2$. Only $a[1]=1 < 2$. $dp[3] = dp[1] + 1 = 2$.

$dp[3] = 2$, extending from index 1.

$i=4$: $a[4]=5$. Predecessors: $a[0]=3, a[1]=1, a[3]=2$ are smaller. Best is $dp[3]=2$. $dp[4] = 3$.

$dp[4] = 3$, extending the subsequence $[1, 2, 5]$.

$i=5$: $a[5]=4$. Predecessors: $a[0]=3, a[1]=1, a[3]=2$ are smaller. Best is $dp[3]=2$. $dp[5] = 3$.

$dp[5] = 3$, extending subsequence $[1, 2, 4]$.

$i=6$: $a[6]=7$. Many predecessors. Best is $dp[4]=3$ (via $a[4]=5 < 7$). $dp[6] = 4$.

$dp[6] = 4$, extending subsequence $[1, 2, 5, 7]$.

$i=7$: $a[7]=6$. Predecessors with smaller value: $a[4]=5, a[3]=2, a[1]=1, a[0]=3$. Best is $dp[5]=3$ (via $a[5]=4 < 6$). $dp[7] = 4$.

$dp[7] = 4$. The LIS length is $\max(dp) = 4$.

Traceback: one optimal LIS is $a[1], a[3], a[4], a[6] = [1, 2, 5, 7]$.

Recolor transition arrows along the optimal path: $1 \to 3 \to 4 \to 6$.

Dim the non-path cells to emphasize the solution: LIS = $[1, 2, 5, 7]$, length 4.

Matrix Chain Multiplication: 5 matrices $M_0 \ldots M_4$ with dimension array $p = [30,35,15,5,10,20]$. Matrix $M_i$ has dimensions $p_i \times p_{i+1}$.

Base case: $dp[i][i] = 0$ for all $i$. Multiplying a single matrix costs nothing.

$dp[0][1]$: only split $k=0$. Cost $= 0 + 0 + 30 \cdot 35 \cdot 15 = 15750$.

$dp[1][2] = 35 \cdot 15 \cdot 5 = 2625$.

$dp[2][3] = 15 \cdot 5 \cdot 10 = 750$.

$dp[3][4] = 5 \cdot 10 \cdot 20 = 1000$.

Diagonal 1 complete. All length-2 chains computed.

$dp[0][2]$: try $k=0$: $dp[0][0] + dp[1][2] + 30 \cdot 35 \cdot 5 = 0 + 2625 + 5250 = 7875$. Try $k=1$: $dp[0][1] + dp[2][2] + 30 \cdot 15 \cdot 5 = 15750 + 0 + 2250 = 18000$. Min: $7875$.

$dp[1][3]$: $k=1$: $0+750+35 \cdot 15 \cdot 10 = 6000$. $k=2$: $2625+0+35 \cdot 5 \cdot 10 = 4375$. Min: $4375$.

$dp[2][4]$: $k=2$: $0 + 1000 + 15 \cdot 5 \cdot 20 = 2500$. $k=3$: $750 + 0 + 15 \cdot 10 \cdot 20 = 3750$. Min: $2500$.

Diagonal 2 complete. All length-3 chains computed.

$dp[0][3]$: check $k=0,1,2$. Best: $k=0$ gives $0 + 4375 + 30 \cdot 35 \cdot 10 = 14875$. But $k=2$ gives $7875 + 0 + 30 \cdot 5 \cdot 10 = 9375$. Min: $9375$.

$dp[1][4]$: check $k=1,2,3$. $k=1$: $0+2500+35 \cdot 15 \cdot 20 = 13000$. $k=2$: $2625+1000+35 \cdot 5 \cdot 20 = 7125$. $k=3$: $4375+0+35 \cdot 10 \cdot 20 = 11375$. Min: $7125$.

Diagonal 3 complete. All length-4 chains computed.

$dp[0][4]$: check all splits $k=0..3$. $k=2$: $7875 + 1000 + 30 \cdot 5 \cdot 20 = 11875$. This is the minimum.

$dp[0][4] = 11875$. The minimum number of scalar multiplications to compute the matrix chain $M_0 M_1 M_2 M_3 M_4$ is $\mathbf{\text{11875}}$11875.

Optimal split: $(M_0 (M_1 M_2)) ((M_3 M_4))$. The path cells are highlighted.