Parallel dynamic programming

Recurrence formulations for various problems, such as finding an optimal order of matrix multiplication, finding an optimal binary search tree, and optimal triangulation of polygons, assume a similar form. In papers by Gibbons and Rytter, and Rytter a CREW PRAM algorithm was given to solve such dynamic programming problems. The algorithm uses O(n⁶/logn) processors and runs in O(log²n) time. In this short note, a modified algorithm is presented that reduces the processor requirement to O(n⁶/log⁵n) while maintaining the same time complexity of O(log²n).