Is it possible to improve every recursive algorithm using dynamic programming?

I am a first year student of CSc who wants to get competitive programming.

Recursion includes the definition and solution of auxiliary problems. As far as I understand, top-down dynamic programming (dp) involves remembering solutions for subprocesses to reduce the time complexity of the algorithm.

Is it possible to use top down dp to increase the efficiency of each recursive algorithm with overlapping auxiliary problems? Where dp won't work and how can I identify this?

+6
source share
1 answer

Short answer: Yes.

However, there are some limitations. The most obvious is that recursive calls must overlap. That is, during the execution of the algorithm, the recursive function must be called several times with the same parameters. This allows you to trim the recursion tree by memoization. That way you can always use memoization to reduce the number of calls.

However, this reduction in calls comes with a price. You need to save the results somewhere. The next obvious limitation is that you need to have enough memory. This is due to a less obvious limitation. Accessing memory always takes some time. First you need to find where the result is stored, and then maybe even copy it to some place. Therefore, in some cases, faster recursion allows you to calculate the result, rather than loading it from somewhere. But this is very implementation specific and may even depend on the operating system and hardware settings.

+6
source

All Articles