4 ms·
> Read wikipedia and it seems to mean....use a recursive function? Yes, that's one (common) approach to dynamic programming. The recursive function call are me
by joz1-k 1y ago
> Read wikipedia and it seems to mean....use a recursive function?
Yes, that's one (common) approach to dynamic programming. The recursive function call are memoized so that previous calculations are remembered for future function calls. Overlapping subproblems become trivial if you can reuse previously computed values. The recursion with memoization is top-down dynamic programming.
- scotty79 1y agoSo all in all pretty basic stuff. Why would anyone worth their salt should have problem with that?
- dgacmu 1y agoThe hard part is realizing that the problem you're solving efficiently maps to a dynamic programming algorithm. You have to spot the opportunity for sub-problem reuse, or else the solution looks something like cubic or exponential (etc.)
- scotty79 1y ago> You have to spot the opportunity for sub-problem reuse Which sounds exactly like what developers do in non boring parts of our job. If anything, the problem is that tests are being tightly timed, while time budget for real world task of this kind is usually more generous. On the other hand business time that company spends with inefficient solution or without one costs a lot of money so I can't blame companies for wanting employee who at least on toy problems can do that quick.