After a while, I managed to find a book that talked about dynamic programming, and I was like "Oh, …

I had the same experience: no one knew of my mentors what "dynamic programming" was and our country-level competition (that had created problems inspired by IOI) required dynamic programming for 2 out of 5 problems. And of course I failed the first time (2004). Then I learned what it was about and aced the next time (2005).

I was part of the hosting team at IOI 1997 in Cape Town and had similar conversations with the participants that you described and also learned about Dynamic Programming there. Your description of it as "recursion + storing results which you can sometimes do iteratively" is the best summary. Good example is iterative Fibonacci algorithm. Another fun anecdote from that time is that we had to take special precautions with the scoring program which connected to the participants machine over the serial port. The previous year one participant had hacked the serial port interface to manipulate the results. :-)

Has there been an "arms race" of sorts with programming contests, as knowledge percolates and harder categories of problems need to be chosen? Since these days dynamic programming is basically table stakes for ICPC-type problems.

Loved your wonderful story—here’s my plain one. I came to programming after I graduated, and I never really understood Dynamic Programming until I watched one of Stanford’s algorithm courses (kudos to MOOCs). But honestly, I’ve never done anything truly useful with it—except that it gave me a new perspective on ordinary things. For example, I found that there may be great wisdom in the Taiji symbol (image here: https://commons.wikimedia.org/wiki/File:Yin_yang.svg ). We can divide the current problem and conquer it at the lower levels (like one of the dots in yin and yang). And of course, those lower levels still contain their own divisions and computations—until there are none left. At the same time, we can also start from the base and build upward (bottom-up), moving toward higher-level computations—where possible divisions await, until eventually one big unified answer emerges. Pretty …

I wonder if you can clear up a memory of mine from IOI 2001. The first day results were delayed, and I seem to remember this is because a contestant encoded the search in one of the problems into a compile time c++ template metaprogram. On the second day, there was then also a compile time limit for solutions, from what I remember. Do you remember any more details of this?

One thing I always wondered is: what makes dynamic programming more "dynamic" than regular programming? Why is recursion "static" but it becomes "dynamic" if you store results?

Oh that's the year I went. Trip down memory lane. I was woefully unprepared. The mobile phone cell summation problem underlined how much I didn't know, and later figuring it out, how much I had to learn; it cemented my love for the field. I just loved the experience.

As a US born native English speaker, I always struggled with the phrase. Eventually I just mentally called it a misnomer as the phrase provided no value to the actual problem set they described.