An optimal sublinear time parallel algorithm for some dynamic-programming problems

We consider the following problem: minimize the time of optimal parallel computations of a dynamic programming problem given by dynamic programming recurrences. By an optimal algorithm we mean here the algorithm whose total work matches the work of the best known sequential algorithm for a given problem (in this case O(n³)). We construct an optimal parallel algorithm which runs in time O(n²/(3 log (n))) with total work O(n³). It is at present the fastest optimal algorithm for the general dynamic programming recurrences.