Every dynamic programming problem I have solved, I first solved as a recursion with a cache, and the answer came out identical. The tabulated version then felt like rewriting working code backwards to satisfy a convention.
Is there a real difference, or is the bottom up form just a style preference?
Accepted Answer
They compute the same thing, and usually you should write the memoised recursion first. But they are not interchangeable, for two reasons.
The recursion uses the call stack, one frame per level. On a problem with a hundred thousand states, that is a stack overflow rather than a slow answer. Tabulation has no stack to blow.
The second is that once the table is explicit, you can often see that each row depends only on the previous one, and throw the rest away. That takes memory from O(n²) to O(n), and the recursive form hides that from you completely.
So: top down to find the recurrence, bottom up when the shape of the table buys you something.
Careful with "dynamic programming is memoisation" as a definition though, because it drops the requirement that actually decides whether either will work.
You need optimal substructure and overlapping subproblems. Caching a recursion with no overlap buys nothing but memory, and caching one without optimal substructure gives a wrong answer quickly instead of a right answer slowly.
The caching is the technique. Those two properties are what make the technique legitimate, and checking them is the part people skip.
One practical difference. Memoisation only computes the states you reach. Tabulation computes all of them. If the reachable set is sparse, top down can be genuinely faster, not just easier to write.
The discussion on each answer is open to members.
Join free to read the rest