Dynamic Programming is important!

[borisyankov]

Dynamic Programming is under the 'Everything below this point is optional' line.

These types of questions are very often used, and every person needs to study. I wouldn't consider them optional.

[jwasham]

I understand, and I was adamant that it was important, too, but for the Google interview, it's not expected. I checked the Yegge article and all the Google coaching notes and interview prep they recommend and they don't even mention it. Much to my surprise. Keep in mind they are only expecting CS 101 knowledge. DP is seen as a bit more advanced.
To continue my adamant stance, I asked my referral about it (twice), and even he said to not worry about it.

Here's why:

1. It can definitely be useful to solve some problems, but it's not required.
2. For many solutions with a dynamic programming solution, there can be other solutions that are good enough to get you hired. Remember, you're being compared against other candidate performance.
3. Coming up with a solid DP solution to a new problem can be difficult to discover, code, test, and get right in 40 minutes.
4. Knowledge of a DP solution to a problem you've seen before isn't testing your ability to solve new problems, just memorization of the solution to an existing problem.

This isn't stopping me from trying some problems, however, but I'm not stressing about it anymore.

[borisyankov]

Gayle McDowell herself is not very clear on that:
https://www.quora.com/Should-I-really-study-and-learn-dynamic-programming-for-google-interviews

On the other hand she, and most Algorithm books do include that topic. HackerRank has a ton of questions about Dynamic Programming too.

I think I understand where this comes from:
'Dynamic Programming' is more of a term used in books and not in practice, but the concept itself is very important.

I would say, there is a decent chance (more than 10-20%) that you are asked a question requiring it, and if you do not optimize correctly, you will get not a O(N) complexity but O(N^2) which is likely a not a good enough solution.

[jwasham]

You make a good point. Since it's valuable, I'll move it to the required, but with a disclaimer. :)

[borisyankov]

To strengthen the argument, LeetCode has 443 programming problems given at actual interviews, 63 of them are tagged 'dynamic programming'.

https://leetcode.com/tag/dynamic-programming/