4 ms·
brute force recursive solution + @lru_cache annotation. works for me every time on leetcode.
by dominotw 6y ago
brute force recursive solution + @lru_cache annotation.
works for me every time on leetcode.
- mettamage 6y agoI've solved some DP problems (I call it: "find the right table/array and then decide whether you feel recursive or iterative"). I know about lru caches. Yet, I'm not fully understanding what your implying with your comment.
- jvanderbot 6y agoOp's saying (I think) that the difference between brute force recursion and DP ( top down ) is memoization, and that the language / library construct lru_cache will perform that memoization for you. Its not a fascinating insight. If you can express a problem as a recursive brute force solution and there's a least a little recalculation involved, you're one step from DP. The lru_cache just does that step. Just google lru_cache edit: "op"
- currymj 6y agoit is a particular part of the Python 3 standard library. it is one extra line of code to automatically memoize a recursive function. you just do: from functools import lru_cache @lru_cache(maxsize=None) def brute_recursive_func(x): ... And you're good to go.
- rmk 6y agoVery nice! I often forget this handy thing during interviews. Good thing to impress your interviewer with :)
- rmk 6y agoOne thing of note: The arguments to the method you are memoizing need to be hashable. For example, if you want to memoize a method call whose parameters include a list, you will get an error!
- anon_tor_12345 6y agoeveryone always says this as if it's some kind of galaxy brain epiphany. it's not because 1) on interviews they want you to explicitly construct the array very often i.e. it's the different between hire and a strong hire exactly because @lru_cache is much easier 2) you can easily blow the stack for real production grade implementations using recursion (think edit distance for genome sequences). you also lose time actually doing the recursion. on the other hand, it's easier to prune the search space with explicit recursion vs tabulation. edit: btw i'll also say that dynamic programming proper, i.e. as a technique for solving optimization problems defined by recurrence relations, uses tables and recursion (fixed points). so good luck understanding something like the linear quadratic regulator if you think it's just @lru_cache https://berkeley-me233.github.io/static/ME233_Sp16_L1_DP_Optimal_LQR.pdf https://berkeley-me233.github.io/static/ME233_Sp16_L1_DP_Opt...
- dominotw 6y ago> on interviews they want you to explicitly construct the array very often i.e. it's the different between hire and a strong hire exactly because @lru_cache is much easier are you serious? someone really asked you to "use array". Beyond stupid if they really did. > you can easily blow the stack for real production grade implementations using recursion recursive solution doesn't automatically mean using a the method stack. you can implement recursive solutions using explicit stack . > dynamic programming proper please. There is no "proper" dynamic programming. Please watch this MIT intro https://www.youtube.com/watch?v=OQ5jsbhAv_M https://www.youtube.com/watch?v=OQ5jsbhAv_M .
- anon_tor_12345 6y agoyou're wrong on all counts but i'm going to be the one to correct you.
- Der_Einzige 6y agoNah, you're the one whose wrong on this one.