News for hackers. Stuff that matters.
Re:Dynamic Programming for Technical Interviews by baobabKoodaa on Friday March 15, 2019 @09:18AM (#19399386)
DP is a general problem solving approach. It's about recognizing which parts of a naive solution have repetition which can be eliminated to improve the time complexity of the solution. Another poster aptly described it as finding states which can be collapsed into one. However you want to think about it,

- DP is a general problem solving approach

- DP is not limited to any particular implementation detail (like my parent poster attempts with "it's just a simple cache mechanism")

- DP is not a "trick" that you can learn and then solve any DP problem

If we have a DP solution, we can write it in many ways. We can write it top-down with recursion and memoization, or we can write it bottom-up without memoization. Whether we use memoization in our solution or not is a minor implementation detail. Both solutions are DP. Other posters seem to make a distinction between these two solutions as if they are entirely different and as if the recursive solution is not dp - this is also incorrect. The challenge in DP tasks is about improving time complexity by recognizing repeated sub calculations.

Re:Dynamic Programming for Technical Interviews by reader5000 on Friday March 15, 2019 @11:40AM (#19400672)
In "Algorithms" [Dasgupta, Papamdimitriou, Vazirani] they state that the memoization (e.g. querying a hash table) can have significant overhead leading to a large constant factor in the big O analysis. On the other hand, the bottom up approach using a table solves all the possible subproblems including ones that are not needed and ones that the recursive approach would avoid. So from a big O perspective the recursive top-down and the table bottom-up approaches are the same but there can be significant constant factor differences.
Re:Dynamic Programming for Technical Interviews by UncleMeat on Friday March 15, 2019 @12:18PM (#19401064)
Then mention this in the interview. I ask an algorithms question that would likely be hated on HN but when candidates tell me the practical difference (API cleanliness, maintainability, performance, extensibility) between approaches that ultimately don't impact asymptotic runtime I love it.
Re:Dynamic Programming for Technical Interviews by baobabKoodaa on Friday March 15, 2019 @12:58PM (#19401601)
This is true. However, both approaches are "dp" if we are talking about the equivalent solution implemented in these different ways.
Re:Dynamic Programming for Technical Interviews by reader5000 on Friday March 15, 2019 @01:10PM (#19401776)
Yeah I thought the recursion+memo wasn't actually "dp" until I looked it up. Recursion without the memo is not DP however since you hit exp running time/memory and the whole point of DP is to avoid this.