Hacker News Reader

Comment by zzzeek | Hacker News Reader

I've never heard of a "dynamic programming algorithm". Read wikipedia and it seems to mean....use a recursive function? The coin problem is an easy recursive problem (I just wrote the code for it to make sure my old brain can still do it).

View on HN

It's usually covered in a first or second year algorithms course. It's a recursive problem definition paired with tabling to eliminate redundant work. Critically, the recursive subproblems have to be overlapping (they'll do some of the same work as the other recursive steps) to see any benefit. You can implement it top-down and add a cache (memoization) or you can implement it bottom-up and fill out the table iteratively rather than through recursion.

If you just implement it recursively without tabling then you end up re-doing work and it's often an exponential runtime instead of polynomial.

To clarify on overlapping, consider Fibonacci:

  F(n) = F(n-1) + F(n-2) # and the base cases

F(n-1) includes F(n-2) in its definition, and both F(n-2) and F(n-1) include F(n-3). If you implement this naively it produces an exponential runtime. Once you add the table, the single initial recursive call to F(n-1) will end up, through its chain of calls, storing the result of F(n-2) and now the implementation is linear instead of exponential.

> Read wikipedia and it seems to mean....use a recursive function?

Yes, that's one (common) approach to dynamic programming. The recursive function call are memoized so that previous calculations are remembered for future function calls. Overlapping subproblems become trivial if you can reuse previously computed values. The recursion with memoization is top-down dynamic programming.

So all in all pretty basic stuff. Why would anyone worth their salt should have problem with that?

The hard part is realizing that the problem you're solving efficiently maps to a dynamic programming algorithm. You have to spot the opportunity for sub-problem reuse, or else the solution looks something like cubic or exponential (etc.)

> You have to spot the opportunity for sub-problem reuse

Which sounds exactly like what developers do in non boring parts of our job. If anything, the problem is that tests are being tightly timed, while time budget for real world task of this kind is usually more generous. On the other hand business time that company spends with inefficient solution or without one costs a lot of money so I can't blame companies for wanting employee who at least on toy problems can do that quick.

The coin problem is like the intro to it. Try some of the codeforces one :skull:

Reply on news.ycombinator.com