When I first read about dynamic programming, I was already familiar with the idea of memoizing a naive recursive program to make it efficient. After that, heari

When I first read about dynamic programming, I was already familiar with the idea of memoizing a naive recursive program to make it efficient. After that, hearing all this talk about oddly-shaped tables was actually kind of irritating. "Why are they going to all this trouble to talk about specific ways of memoizing recursive functions?" I asked myself, rhetorically. "Using a hash table has the same amortized asymptotic complexity, and this shouldn't be hard." It just seemed like way too much artificial complexity for what was, at heart, a remarkably simple and easy technique. This still bothers me. Perhaps it's a historical relic from the ancient times when dynamic programming was done by hand, and those oddly-shaped tables were needed to make it easier for the people working as computers.