This is going to be a short story, hopefully this trick will allow someone to optimize their algorithm further during an onsite interview. The main tenet of Dynamic Programming is to break down a complex problem into sub-problems, memoize those solutions in order not to recompute the same things multiple time, henceforth reducing the algorithm complexity.