Sparse dynamic programming I: linear cost functions David Eppstein, Zvi Galil, Raffaele Giancarlo, and Giuseppe F. Italiano J. ACM 39(3):519–545, Jul 1992 Mathematical Reviews 93i:90107a, 1993 Reviewed by Moshe Sniedovich