21–30 of 225 posts
So "DP" is just recursion with memoization? Or an I missing another piece? Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
Earlier quoted context omitted.
So, what about something relatively straightforward? Like Fibonacci. Is it "DP" if I recurse+cache?
Yep, it's still certainly DP, in the same sense that 1 + 1 is addition, but understanding 1 + 1 doesn't necessarily mean that you've mastered addition.
Say I, at runtime, build a table of function pointers. Based on some attribute/test of the input that suggests a specific type of function is faster for that type of input.
If it's faster, but not exponentially faster than a naive solution...is that "dynamic"?
> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…
I think dynamic programming is in fashion because of the rise of reinforcement learning among the buzzword savvy.
So "DP" is just recursion with memoization? Or an I missing another piece? Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
Dynamic Programming can be done using Memoization (top-down; aka recursively) or Tabular method (bottom-up). So what's the difference?
When you see top-down, it means to start from the root of the problem and recursively descend to the base case. As you pop up the stack, you will either calculate and store the result or look up the value in the cache. e.g., in the Fibonacci sequence, check to see if fib(4) was already calculated. No? Calculated and store it so the next time you come across this, you can use the result and not worry about processing fib(1), fib(2), fib(3), etc.
When you see bottom-up, think about filling out a table from the upper left corner column by column then row by row. To speed performance, you'll look at prior values, the value in the column above vs. column to the left vs. or column diagonally to the left. I know this sounds a bit strange, but if you solve the following problems, you'll see a repeating pattern.
Edit Distance 0/1 Knapsack Rod Cutting Longest Common Subsequence Longest Path in Matrix Coin Change
I've been writing about this in detail. Eventually I'll publish my writing to help others. I solve ~20 problems using Memoization and the Tabular method. As I solve each problem, I compare the solutions with prior problems showing the pattern. What I want to do is help people spot "patterns" vs. memorizing algorithms that are very problem specific.
> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…
>This is sad and a little surprising to me. I think dynamic programming is in fashion because of the rise of reinforcement learning among the buzzword savvy.
Shriram Krishnamurthi explains it best:
https://blog.racket-lang.org/2012/08/dynamic-programming-ver...
> problems on DP are pretty standard in most product-company-based hiring challenges This is sad and a little surprising to me. I've always thought of DP problems as being obviously terrible interview questions, even among the different types of algo questions (which are already heavily criticized). Candidates who have learned DP in school usually find them really easy, and candidates who haven't usually don't even h…
That said, if a candidate goes to LeetCode or some other site to practice all the DP problems, then it's possible that the candidate can only solve DP problems without gaining other abilities.
Earlier quoted context omitted.
Based on my understanding, the key difference with DP is that you build the solution bottom up instead of top-down. For example, in case of computing the factorial of 10 recursively, you would start at fact(10) and move down to the base case, fact(1). With DP, you would start with fact(1) and compute succesive results based on computed ones, all the way up to fact(10). Following on from this, you usually build up the…
I've done a lot of programming contest stuff, and at least when speaking casually, I've always heard DP as referring to either the top-down approach or the bottom-up approach. They have their tradeoffs (though usually top-down is better because it's easier to implement), but they're both DP. It may be that you're technically not supposed to use the term "DP" for the top-down variant, but in practice people use the te…
Bottom up is faster, usually shorter to code, and allows certain kinds of optimizations you can't do with top down (sliding window, convex hull trick, etc).
Top down frees you from needing to think about order of computation, and also allows a different set of optimizations from bottom up (divide & conquer).
So "DP" is just recursion with memoization? Or an I missing another piece? Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
1. Solutions are typically written bottom up 2. The meat of the problem is understanding how to formulate it such that this "recursion" is possible. Point two is often non-trivial so your "just" -- while technically correct -- isn't true in practice. If you solve a variety of medium and difficult DP problems, it will be clear why. Eg: https://www.hackerrank.com/domains/algorithms?filters%5Bsubd... (I have no affiliat…