3 ms·
Why are you assuming that the recursive solution is less clear?
by darzu 8y ago
Why are you assuming that the recursive solution is less clear?
- blackflame7000 8y agoExperience, tells me so. To be fair some items like Fibonacci numbers are probably equally as clear.
- deleted 8y ago[deleted]
- danmg 8y agoDivide an conquer type algorithms usually lend themselves to naive recursive solutions more often than not. DP usually requires you to find that solution and find some clever relationships that allow you to build up the final solution from the bottom up.
- blackflame7000 8y agoSure there are some problems that lend themselves nicely I already said as much. But in general for an INTERVIEW problem, it as a poor skill to dwell on or even bother testing for since real-world coding is simply not done that way or God forbid what might happen when someone not as capable (but cheaper or younger) has to take over your code base.
- danmg 8y agoWe're talking about ACM style search problems that are used for interviews, and not about iterating over an array recursively. For these, the recursive formulation is the naive and inefficient way of solving them.
- kolpa 8y agoIf you systematically analyze it, you don't need to be clever on a per-problem basis. Every recursive solution can me methodically converted to DP.
- danmg 8y agoYes, it's a form of pattern recognition. You can get very good at it and do it mechanically, just like solving integrals. You can spend a lot of time getting very good at them, or you can just use memorization/rsolve just like you can just use maple or evaluate them numerically for integrals.
- deleted 8y ago[deleted]