Java dynamic programming: for this project, we will implement Matrix Chain Multiplication

Exercise 15.2-2:

Figure 15.5

PRINT-OPTIMAL-PARENS(s, i, j) MATRIX-CHAIN-ORDER(p) 1 n = p.length-1 2 let m[1..n, 1..n] and s[1..n-1, 2.n] be new tables2 print "A" i 3 fori-1 to n 3 else print "C" 4 PRINT-OPTIMAL-PARENS(s, ?, s[i,j]) 5 PRINT-OPTIMAL-PARENS(s, s[i,j]+1,j) 5 for l- 2 to n /I I is the chain length 6 for i -1 to n- 1 6 print ") j=i+1-1 8 m[i, j] 9 for k i to j-1 10 q = mli, k] + m[k+1, j] + pi-1 pp, 11 ifq?m[i,j] 12 13 14 return m and s m[i, j] = q sli, jl k