I am a first year undergraduate CSc student who is looking to get into competitive programming.
Recursion involves defining and solving sub problems. As I understand, top down dynamic programming (dp) involves memoizing the solutions to sub problems to reduce the time complexity of the algorithm.
Can top down dp be used to improve the efficiency of every recursive algorithm with overlapping sub problems? Where would dp fail to work and how can I identify this?
The short answer is: Yes.
However, there are some constraints. The most obvious one is that recursive calls must overlap. I.e. during the execution of an algorithm, the recursive function must be called multiple times with the same parameters. This lets you truncate the recursion tree by memoization. So you can always use memoization to reduce the number of calls.
However, this reduction of calls comes with a price. You need to store the results somewhere. The next obvious constraint is that you need to have enough memory. This comes with a not-so obvious constraint. Memory access always requires some time. You first need to find where the result is stored and then maybe even copy it to some location. So in some cases, it might be faster to let the recursion calculate the result instead of loading it from somewhere. But this is very implementation-specific and can even depend on the operating system and hardware setup.
