Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dynamic Programming vs. Divide-and-Conquer (2018)

trekhleb.dev

Post reply on HN
Print view View original

71–80 of 120 posts

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#71

Post by rory »

ketzu wrote: post #54
da39a3ee wrote: post #32

Looks great, bookmarked. A big problem with explaining/learning this area is the name. Names are important but unfortunately the name "dynamic programming" is, according to the people responsible for choosing the name, just BS that they made up one day for their employer.

> unfortunately the name "dynamic programming" is, according to the people responsible for choosing the name, just BS that they made up one day for their employer. For people interested, Richard Bellman who apparently came up with the name, put down the story in his autobiography which is cited on wikipedia: https://en.wikipedia.org/wiki/Dynamic_programming#History "I spent the Fall quarter (of 1950) at RAND. My firs…

I originally had trouble with this term because I learned about it after learning the unrelated (afaict) terms "dynamic programming language" and "dynamic typing". So perhaps it's not so much that dynamic programming was a bad choice when it was named, but that we've overloaded the term "dynamic" too much since then.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#73

Post by mettamage »

dominotw wrote: post #70
anon_tor_12345 wrote: post #60

i'm late to the comments but hopefully this helps someone: i struggled with DP as much as anyone. i read all of the standard resources (CLRS, vazirani, kleinberg, etc), watch all the youtube videos, did all of the practice problems in the books , and still couldn't solve the kinds that are asked on interviews. i even went as far as emailing kleinberg for help. what made it basically unconsciously fluent for me (i.e.…

brute force recursive solution + @lru_cache annotation. works for me every time on leetcode.

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.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#74

Post by jorblumesea »

anon_tor_12345 wrote: post #60

i'm late to the comments but hopefully this helps someone: i struggled with DP as much as anyone. i read all of the standard resources (CLRS, vazirani, kleinberg, etc), watch all the youtube videos, did all of the practice problems in the books , and still couldn't solve the kinds that are asked on interviews. i even went as far as emailing kleinberg for help. what made it basically unconsciously fluent for me (i.e.…

Take a problem that you could brute force. Does it have repeating sub problems? If so, it's a candidate for DP.

DP and Greedy problems are the hardest to nail because they are the broadest and widest category of problems. Almost everything can be a DP problem.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#75

Post by jvanderbot »

mettamage wrote: post #73
dominotw wrote: post #70

Earlier quoted context omitted.

brute force recursive solution + @lru_cache annotation. works for me every time on leetcode.

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.

Op'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"

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#76

Post by currymj »

mettamage wrote: post #73
dominotw wrote: post #70

Earlier quoted context omitted.

brute force recursive solution + @lru_cache annotation. works for me every time on leetcode.

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.

it 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.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#77

Post by crazypython »

anon_tor_12345 wrote: post #60

i'm late to the comments but hopefully this helps someone: i struggled with DP as much as anyone. i read all of the standard resources (CLRS, vazirani, kleinberg, etc), watch all the youtube videos, did all of the practice problems in the books , and still couldn't solve the kinds that are asked on interviews. i even went as far as emailing kleinberg for help. what made it basically unconsciously fluent for me (i.e.…

DP is basically brute-force but you can reuse some of the subproblems.

Another approach is trying to find a "starting point" and solving subproblems. Imagine an array of problems and starting at the left.

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#79

Post by anon_tor_12345 »

dominotw wrote: post #70
anon_tor_12345 wrote: post #60

i'm late to the comments but hopefully this helps someone: i struggled with DP as much as anyone. i read all of the standard resources (CLRS, vazirani, kleinberg, etc), watch all the youtube videos, did all of the practice problems in the books , and still couldn't solve the kinds that are asked on interviews. i even went as far as emailing kleinberg for help. what made it basically unconsciously fluent for me (i.e.…

brute force recursive solution + @lru_cache annotation. works for me every time on leetcode.

everyone 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_Opt...

Re: Dynamic Programming vs. Divide-and-Conquer (2018)

#80

Post by anon_tor_12345 »

crazypython wrote: post #77
anon_tor_12345 wrote: post #60

i'm late to the comments but hopefully this helps someone: i struggled with DP as much as anyone. i read all of the standard resources (CLRS, vazirani, kleinberg, etc), watch all the youtube videos, did all of the practice problems in the books , and still couldn't solve the kinds that are asked on interviews. i even went as far as emailing kleinberg for help. what made it basically unconsciously fluent for me (i.e.…

DP is basically brute-force but you can reuse some of the subproblems. Another approach is trying to find a "starting point" and solving subproblems. Imagine an array of problems and starting at the left.

>DP is basically brute-force but you can reuse some of the subproblems.

this is like saying

"integration is basically weighing a bunch of buckets but the buckets are really small"

cool but that won't help you find the correct trig sub to perform the integral. anyone that's familiar with the calc grind knows getting a good grade for the anti-derivative (indefinite integral) module is about the number of exercises you've done rather than the conceptual understanding.

Post reply on HN