Since I have time during my vacation, I wanted to spend some fun time with my laptop solving Mathematical/computer programming problems. I found Project Euler website while checking del.icio.us popular bookmarks about algorithms. The first problem I solved was Problem #208 Robot Walks. I chose to solve it because I liked the title (it reminded me the problems that I worked on while I was getting ready for IOI during high school) and it was one of the difficult ones on the site (tough it turned out to be Relatively easy). I will not tell you how I solved the problem in case you want to try yourself . It took some time to figure out to model the problem. After finding the solution I tried  a brute force approach. Even for a limited set it took more than 10 sec to solve. I tried the full set but I had to stop after couple of minutes without any answer. Then I figured out there were many small sub problems that my algorithm re calculate again and again. To save time I needed to calculate once and save it and use recalculated values instead of trying to re calculate. I calculated the space to store all possible combinations and I needed an array with a size less than 1 GB which I could allocate on my laptop ... anyway at the end , my small program found the solution under 500 milliseconds. This is the beauty of dynamic programming. You can find a nice explanation of dynamic programming here .

12 Years ago

I remember during high school I worked on PCs that had 2-4 MB of ram. When I was working on this kind of problems back then, I almost never considered allocating memory to save sub problem results since memory was a limited resource. I usually spent more time on finding a more fine-tuned algorithm with many heuristics to save on CPU time.  It is not the case anymore, this is a mind shift for me.

Aziz Cagatay Kurt