Dynamic programming to minimize the maximum number of open stacks

We give a dynamic–programming solution to the problem of minimizing the maximum number of open stacks. Starting from a call–based dynamic program, we show a number of ways to improve the dynamic–programming search, preprocess the problem to simplify it, and determine lower and upper bounds. We then explore a number of search strategies for reducing the search space. The final dynamic–programming solution is, we believe, highly effective.