Abstract
This paper presents parallel algorithms for the dynamic programming problem on systolic arrays. The dynamic programming problem when implemented sequentially takes O(n
3
) time steps. In this paper, an algorithm that runs on a linear array machine in O(n
2
) time, using O(n) processors is presented. Also an algorithm that runs on a mesh connected computer in O(n) time steps, using O(n
2
) processors is being studied. Both algorithms are optimal in terms of time and cost.
