Dynamic programming is essentially a tradeoff of space for time. Repeatedly re-computing a given quantity is harmless unless the time spent doing so becomes a bottleneck in the performance. In this case we should better be storing/caching the previously calculated values and looking them up when needed instead of re-computing.
Think about computing a Fibonacci number by recursion:
Fn = Fn-1 + Fn-2 (with F0 = 0, F1 = 1)
Lets explore the two different solutions. one without the caching and other with caching.
read more here.
