I got really good at dynamic programming problems but then none of the companies I interviewed with asked me a dynamic programming problem. These were large tech companies and well funded startups. Perhaps it was just luck.
Questions with DP solutions are usually not particularly great for interviews. They usually don't have any solutions in-between brute force and DP. If somebody doesn't come up with a DP solution you, as an interviewer, just learned that they don't know DP, but it doesn't give you too much useful signal on the candidate's skills. DP is just kind of a trick that you can learn to solve this specific type of problems, but knowing the trick is not something that FAANG companies want to test for.
I tell interviewees to practice some dynamic programming problems because dynamic programming questions are the least intuitive, and it's good to be prepared in case that's what you get asked.
For the same reason though, I think they make for terrible interview questions - very much dependent on knowing a specific "trick" that doesn't actually come up often in day to day coding.
DP as a paradigm is very interesting. From a high level view, one can appreciate the essential concepts that make it work, with things like memoization, optimal substructure, etc. It's also interesting how it relates to shortest paths problems, and greedy algorithms.
However, as you said, actually trying to solve DP problems relies on knowing the trick, and the tricks varies almost wildly from problem to problem. They're unintuitive, and difficult to derive normally. The intuition you gain from one of them could be entirely useless, or, worse, counterintuitive for another. I personally think, they shouldn't be used for interviews because being able to solve them seems to be more a matter of luck than actual competence.
DP solutions were really in vogue for awhile, and seem to be asked less now. I heard a completely unsubstantiated rumor that FB found them to cause high false negatives because they're such a tricky and specific problem type. Also, once you know the "one trick" to solving them they don't help illuminate candidate thinking.
Partially luck and maybe you never solved it with a DP solution. There are problems for which DP will give an answer but it isn’t a hard requirement for you to come up with it.
I’ve received quite a few DP problems in my time interviewing.
Then again, I feel like saying I’m unusual. I’ve received a lot of very difficult problems. Almost like the people are trying to set me up for failing. ;)
