  It has been shown that the parallel Lattice Linear Predicate (LLP) algorithm
solves many combinatorial optimization problems such as the shortest path
problem, the stable marriage problem and the market clearing price problem. In
this paper, we give the parallel LLP algorithm for many dynamic programming
problems. In particular, we show that the LLP algorithm solves the longest
subsequence problem, the optimal binary search tree problem, and the knapsack
problem. Furthermore, the algorithm can be used to solve the constrained
versions of these problems so long as the constraints are lattice linear. The
parallel LLP algorithm requires only read-write atomicity and no higher-level
atomic instructions.
