I'm interested in the question of how and when naive dynamic programming techniques can be speeded up. One example is when the quadrangle inequality holds but that is a fairly restricted condition. Can anyone point me to a summary of elementary techniques which hold more widely? Thank you,
Paul