GATE CSE Dynamic Programming – Algorithms Practice Test | Set 1

Updating the 1D array from right to left ensures that values from the previous row K[i-1][...] are preserved before being overwritten by row i.

$Dimensions p = [10, 30, 5, 60, 8].
- m[1,2] = 10*30*5 = 1500
- m[2,3] = 30*5*60 = 9000
- m[3,4] = 5*60*8 = 2400
- m[1,3]: min((A1)(A2A3) = 0 + 9000 + 10*30*60=27000, (A1A2)(A3) = 1500 + 0 + 10*5*60=4500) = 4500.
- m[2,4]: min((A2)(A3A4) = 0 + 2400 + 30*5*8=3600, (A2A3)(A4) = 9000 + 0 + 30*60*8=23400) = 3600.
- m[1,4]: min(k=1: 0 + 3600 + 10*30*8=6000; k=2: 4500 + 2400 + 10*5*8=6900; k=3: 4500 + 0 + 10*60*8=9300) = 4500.
Minimum scalar multiplications = 4500.$

The DP table has O($n^2)$ entries. To compute each entry m[i, j], we try O(n) possible split points k. Thus, total time is O($n^3)$.

To split product $A_{i}$...$A_{j}$ at k, cost is cost($A_{i}$...$A_{k}$) + cost($A_{k+1}$...$A_{j}$) + cost of multiplying resulting matrices ($p_{i-1}$ * $p_{k}$ * $p_{j}$).

Common subsequences of length 4 include 'BDAB', 'BCAB', and 'BCBA'. Length = 4.