4 ms·
I'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,
by mettamage 6y ago
I'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!