Dynamic programming on two-dimensional systolic arrays (Q1110461)

Given w(i,j), \(1\leq i<j\leq n\), and \(c(i,i+1)\), \(1\leq i<n\), the problem is to compute \(c(i,j)=w(i,j)+\min_{i<k<j}\{c(i,k)+c(k,j)\}\), for \(1\leq i<j\leq n\). We show that this dynamic programming problem can be solved in optimal time \(T=2n\) on a systolic array whose size \(\frac{1}{8}n^ 2+O(n)\) is two times smaller than the number of processors required by the best previously known solution.