  Dynamic programming problems have wide applications in real world and have
been studied extensively in both serial and parallel settings. In 1994, Galil
and Park developed work-efficient and sublinear-time algorithms for several
important dynamic programming problems based on the closure method and matrix
product method. However, in the same paper, they raised an open question
whether such an algorithm exists for the general GAP problem. % In this paper,
we answer their question by developing the first work-efficient and
sublinear-time GAP algorithm based on the closure method and Nested Dataflow
method. % We also improve the time bounds of classic work-efficient,
cache-oblivious and cache-efficient algorithms for the 1D problem and GAP
problem, respectively.
