Travelling plan between two places
Before proving a lower bound you have to formalize your computational model. This can be done in several ways for dynamic programming. The pioneer here is Allan Borodin, who came up with priority branching trees. Buresh-Oppenheim et al. extended this to the strong model of priority branching programs. Jukna considered incremental dynamic programming algorithms,tropical circuits and tropical switching networks. The last model is particularly simple, and Jukna proves some tight results for it, so you may be able to prove that your algorithm is optimal for that model.