We consider discrete optimization problems in which the only exploitable feature of the objective function is a limited form of decomposability. “Nonoverlapping comparison algorithms” are defined as a model of procedures which decompose the problem and apply Bellman’s principle of optimality. Nonserial dynamic programming (DP), a simple elimination procedure, is shown to be optimal among all nonoverlapping comparison algorithms, including nondeterministic algorithms. These results can give an exponential lower bound on the shortest admissible proof that a solution is optimal. Furthermore, if part of the search space is ruled out, a subset of the comparisons made by DP optimally searches the remainder. We suggest that the running time of DP is a useful measure of the “interaction complexity” of a problem, and that because of its simplicity DP is of practical as well as theoretical interest.