Dynamic Programming is just a fancy way of saying memoization or caching - remembering stuff to save time later. If you have already computed a function, map the given parameters to the result, and you can use this information later without calculating the whole function again if the parameters are the same.
Those who cannot remember the past are condemned to repeat it. - Dynamic Programming
There are two ways of using dp, one in recursion and the other in iteration.
It’s easier to write it in recursion since each time the function gets called you can check whether it’s calculated before.
But often, you will see the iterative approach used because recursion usually takes a lot of stack memory.
For a better understanding of these two approaches, check out the 100 seconds of DP.
Dynamic Programming sounds scary to beginners in competitive programming, but this is the video I wish it existed when I started practising DP. It's a really helpful technique all the time!
Hope you have enjoyed the video!
