Didn't You Get the Memo?

I am competing in Google Code Jam. One of the practice problems available in the contest area is called Shopping Plan. The problem is to find the minimum cost for buying a number of items. Each item is available in one or more stores, possibly at different prices. Perishable items must be dropped off at the house before going to the next store. Driving around uses up gas, which is not as free as it used to be. My first attempt at a solution was a Python implementation of the A* search algorithm. The computer ran out of memory. In retrospect, I should have excluded the previously visited stores from the search state. A friend of mine attempted a brute force solution, also without success.

I read up on Shopping Plan in a couple of discussion group threads, where people suggested using either Dijkstra's algorithm (closely related to A*) or dynamic programming. I wrote a new Python program that memoized the minimum costs found so far. It worked. It was right. It was slow. I rewrote the program in C++. It was faster. I changed the program to store memoized costs using vectors instead of maps. It was fast.