recursion - Can every recursive algorithm be improved with dynamic programming? -


i first year undergraduate csc student looking competitive programming.

recursion involves defining , solving sub problems. understand, top down dynamic programming (dp) involves memoizing solutions sub problems reduce time complexity of algorithm.

can top down dp used improve efficiency of every recursive algorithm overlapping sub problems? dp fail work , how can identify this?

the short answer is: yes.

however, there constraints. obvious 1 recursive calls must overlap. i.e. during execution of algorithm, recursive function must called multiple times same parameters. lets truncate recursion tree memoization. can use memoization reduce number of calls.

however, reduction of calls comes price. need store results somewhere. next obvious constraint need have enough memory. comes not-so obvious constraint. memory access requires time. first need find result stored , maybe copy location. in cases, might faster let recursion calculate result instead of loading somewhere. implementation-specific , can depend on operating system , hardware setup.


Comments

Popular posts from this blog

resizing Telegram inline keyboard -

command line - How can a Python program background itself? -

php - "cURL error 28: Resolving timed out" on Wordpress on Azure App Service on Linux -