8 ms·

Sri Lankan here. I used to compete in the IOI (International Olympiad in Informatics), back in the '90s. I aced the competition in Sri Lanka, but I failed to w

Sri Lankan here. I used to compete in the IOI (International Olympiad in Informatics), back in the '90s. I aced the competition in Sri Lanka, but I failed to win a medal the first time I competed internationally. I solved several problems with recursion, but these failed to complete within the strict time limits allowed. One of the contestants from another country told me: "You needed dynamic programming to solve problems 1 and 5." I then spent the next year trying to figure out what dynamic programming was. The folks over here weren't familiar with the term. In fact, I was often asked "did you mean dynamic memory allocation?" After a while, I managed to find a book that talked about dynamic programming, and I was like "Oh, it's recursion + storing results" and "Ah, you can also do this iteratively in certain circumstances" Bottom line, armed with this new knowledge, I ended up winning a gold medal at IOI 2001. Fun times.

deaddodo 1y ago
Technically, "dynamic programming" (god, I hate that term) is focused on memoization/tabulation. It doesn't necessarily require recursion or an iterative approach, although they almost always go hand-in-hand in common leetcode/hackerrank/etc exercises.
zekica 1y ago
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).
snthpy 1y ago
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. :-)
- npsomaratna 1y ago
  Nice! I guess you must know Bruce Merry. Once, when practicing, I kept on hitting my head on a problem. On the spur of the moment, I decided to fire off an email to Bruce (given his track record, I was like "if anyone can figure this out, he can"). I was shocked (and very pleased) to get a reply a few days later outlining his thought process and how he went around solving the problem. I used to know the ZA team leaders as well (after competing, I was a team leader for several more years).
  - snthpy 1y ago
    Yes, I do indeed know Bruce. He won the national Maths and Computer olympiads in my final year of school even though he was 4 grades below me and had just started high school. :-D
- BobbyTables2 1y ago
  The term always made me insufficient as I always assumed it meant much more and I just didn’t understand how. In the Fibonacci example, it seems more like common sense to avoid recomputing expensive things. Instead we should give derogatory names to the inefficient implementations, not an opaque name to the only sane implementation.
krackers 1y ago
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.
- paldepind2 1y ago
  Yes, absolutely. I did programming competitions back in high-school (around 10 years ago) and common folklore was that back in the days knowing dynamic programming could win you a medal, but today it was just basic expected knowledge.
  - bubblethink 1y ago
    There's a lot of variety in DP. Knowing about DP doesn't help much with solving DP problems. I'm sure you've seen all the fun problems on codeforces or leetcode hards. The one quote I remember from Erik Demaine's lecture on DP is where he comments, "How do we solve this with DP ? - With difficulty."
  - npsomaratna 1y ago
    That's my impression as well. I think it's because access to knowledge has become a lot easier, so contestants know more; plus, the competitions themselves have become more organized. For example, last I checked, the IOI had a syllabus outlining the various algorithms contestants needed to know. During my time, it was more of a wild west.
  - kindkang2024 1y ago
    That's how Competition Makes All Great Again. Looks like it's by God's design. ^_^
kindkang2024 1y ago
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 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 useless for its actual usage here, isn’t it? ^^
- matsemann 1y ago
  Dynamic programming is for me one of the things that really scratched an itch and made me start liking programming. The invariant/inductions of composing smaller things into a bigger solution is so elegant. I do feel dynamic programming influences how I solve problems in my work. How, if you compose the problem correctly, it can never reach a fault state in a sense. Not sure if I'm able to explain what I mean, but for instance I recently refactored an old application at work that had lots of bugs, was hard to grasp and had loads of error checking code / asserts. However, by composing it a bit differently, modeling it properly, I could remove swaths of code / defensive programming because I with the help of the compilator now can guarantee the base cases holds etc. Edit: one a bit contrived example might be an Order. If you have one big model tracking the lifetime of an order, some fields will have to be null until they have a value. For instance a field sent_at_time. Then you have a function that generates an email to the customers, which uses that field. How do you handle that field possibly being null? Do you say "I know that at this point in time, this field is always set since the email is generated after sending" and tell the compiler to ignore the possibly null value? Or do you handle the possible null with some error handling / fallback value, that in practice is dead and cluttered code and will just confuse a future developer seeing it with questions like "how can this happen"? With the lessons from dynamic programming in mind, I think both are bad solutions. You want to be able to go from state n to n+1 with safety (order purchased, ordered sent, email sent). So model it in a way that the email sending code only ever can get an order in the correct previous state as input. Then if the assumption were to break in the future (maybe some orders are digital and the email is sent without the order having been physically sent), that breaking assumption will immediately be obvious in how the state/models are composed, and not in runtime when either the not-null-assert fails or the emails start having the fallback value.
nicknash 1y ago
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?
- xandrius 1y ago
  That sounds very smart :D
  - amelius 1y ago
    But aren't the programs given access to the problem data _after_ the program has been compiled?
    - colechristensen 1y ago
      There are plenty of opportunities to precompute _everything_ for a certain class of problems.
    - fer 1y ago
      Sure, but the input might be bounded/finite, or the operations needed similarly constrained (e.g. trigonometry operations). Then you can offload lots of the computation to the compilation, sometimes all of it.
    - SkiFire13 1y ago
      Yeah, but they didn't precompute the solution for that specific program data, they precomputed the solution for all possible ones, and then selected the correct one when the program data was provided.
- npsomaratna 1y ago
  No, sorry. I vaguely remember compile time limits, but they were high enough (30 seconds, I think?) that I didn't bother worrying about them (at least, that's my memory).
mort96 1y ago
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?
- sidewndr46 1y ago
  As others have mentioned the term was chosen to be distinctive and attractive.
- bazoom42 1y ago
  According the article, the term “dynamic” was chosen because it has positive connotations.
  - moffkalast 1y ago
    [flagged]
    - jagged-chisel 1y ago
      Two hard problems in computer science…
      - fragmede 1y ago
        1. Cache invalidation 2. Naming things 3. Off-by-one errors
        lvncelot 1y ago
        0. Race conditions
        cluckindan 1y ago
        4: Threconcadiparaurrenllecy, lism.ng,
    - 1y ago
ncruces 1y ago
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.
mrits 1y ago
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.
Sesse__ 1y ago
For my first programming competition (the national ICPC prequalifier, in 2002), I asked my teammates (who I didn't know very well, we had just cobbled together a team) a couple of minutes before the contest what this dynamic programming thing was. One of them was “oh, it's only caching the output of a recursive function” (technically, that's memoization, but who cares). I ended up solving a problem using DP a couple of minutes before the deadline, which was enough to get us to 3rd and to ICPC. Fun times.
aljgz 1y ago
In the university, we had a team for ACM ICPC. We helped our professor organize a local competition, to encourage more people to practice. We participated in that competition, of course. One question would give you a few numbers no greater than 13, and you would output the number of ways to put N queens on the cheeseboard of those sizes. Not a difficult problem, but our first implementation, needed 2 minutes while time limit was 1 minute. We could optimize, but we decided to run it for all possible numbers, write a new program with just a switch-case. This was q perfectly legal move. We could see his face while judging our submission, his huge surprise when code ended in milliseconds, his look of admiration at us, the curiosity about the solution, and finally his reaction when he checked out our code. Priceless.
- ivan_gammel 1y ago
  Fun enough, in commercial software engineering your solution won’t raise eyebrows as something routine and expected, but an efficient algorithm could do.
  - ape4 1y ago
    Its called https://en.wikipedia.org/wiki/Memoization https://en.wikipedia.org/wiki/Memoization
    - pvitz 1y ago
      More like "precomputed table" and "table lookup"...
    - marcosdumay 1y ago
      Memoization is the kind of dynamic programming the first post on the thread is talking about.
- TheJoeMan 1y ago
  Had a similar problem in a highschool comp. sci. class with a maze-following algorithm where you got points off for back-tracking. Turns out your code could pre-fetch the entire maze before making a move, which I think goes against the spirit of the exercise.
radicalbyte 1y ago
I had to laugh hard the first time I heard about it, I mean it's a really obvious technique if you've ever done low-level programming on limited machines as it's very close to something we used to do all the time - calculate result tables and use lookups which we built in to our code. Trades memory for CPU when it's worth it. Dynamic programming takes the same idea but does it at runtime.
- bo1024 1y ago
  To be fair, DP generally also involves recursion in some way. You could describe it as a lookup table where, to fill in later entries of the table, you need to use the earlier entries.
hinkley 1y ago
I found this video very helpful: https://m.youtube.com/watch?v=oBt53YbR9Kk https://m.youtube.com/watch?v=oBt53YbR9Kk Yes, it is 5 hours long. At least 4 of those are worth it. Many people confuse caching with DP. I’ve had that conversation too often. I think it’s down to the memoization examples people choose being too toy and just looking like caching. Caching is global shared state, whereas memoization can be scoped to the current calculation and still be useful. But they always skip over tabulation, which is where I believe DP distinguishes itself.
- bjourne 1y ago
  But dp is a form of caching, no? It sacrifices space by caching intermediate results to compute successive results. The only reason it is called dp is because the "inventor" (Iirc Bell) needed a cool name.
  - hinkley 1y ago
    No, memoization is not caching. That’s a reductive understanding that causes no end of trouble. Caching is global shared state. It brings nearly every problem that global shared state brings with it. If you conflate the two you miss all of the advantages of DP and “just use caches”. Memoization in the scope of DP (some languages misuse the word in their APIs) is acknowledging that a problem is self recursive and eliminating the duplicate work by either inverting the problem or storing previously calculated values. These are usually call graph scoped. Nobody else sees the value. For instance in the case of solving Fibonacci with iteration, you need only remember the previous two values, which you store in registers. There is no table. There is no O(n) storage space. Again, tabulation is when the contrast becomes stark. You’re creating an array where the relationship between the values contains information that makes the calculations cheap.
    - bjourne 1y ago
      No definition of "caching" I know imply global shared state. Local private caches are commonplace.

deaddodo 1y ago

Technically, "dynamic programming" (god, I hate that term) is focused on memoization/tabulation. It doesn't necessarily require recursion or an iterative approach, although they almost always go hand-in-hand in common leetcode/hackerrank/etc exercises.

zekica 1y ago

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).

snthpy 1y ago

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. :-)

npsomaratna 1y ago
Nice! I guess you must know Bruce Merry. Once, when practicing, I kept on hitting my head on a problem. On the spur of the moment, I decided to fire off an email to Bruce (given his track record, I was like "if anyone can figure this out, he can"). I was shocked (and very pleased) to get a reply a few days later outlining his thought process and how he went around solving the problem. I used to know the ZA team leaders as well (after competing, I was a team leader for several more years).
- snthpy 1y ago
  Yes, I do indeed know Bruce. He won the national Maths and Computer olympiads in my final year of school even though he was 4 grades below me and had just started high school. :-D
BobbyTables2 1y ago
The term always made me insufficient as I always assumed it meant much more and I just didn’t understand how. In the Fibonacci example, it seems more like common sense to avoid recomputing expensive things. Instead we should give derogatory names to the inefficient implementations, not an opaque name to the only sane implementation.

krackers 1y ago

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.

paldepind2 1y ago
Yes, absolutely. I did programming competitions back in high-school (around 10 years ago) and common folklore was that back in the days knowing dynamic programming could win you a medal, but today it was just basic expected knowledge.
- bubblethink 1y ago
  There's a lot of variety in DP. Knowing about DP doesn't help much with solving DP problems. I'm sure you've seen all the fun problems on codeforces or leetcode hards. The one quote I remember from Erik Demaine's lecture on DP is where he comments, "How do we solve this with DP ? - With difficulty."
- npsomaratna 1y ago
  That's my impression as well. I think it's because access to knowledge has become a lot easier, so contestants know more; plus, the competitions themselves have become more organized. For example, last I checked, the IOI had a syllabus outlining the various algorithms contestants needed to know. During my time, it was more of a wild west.
- kindkang2024 1y ago
  That's how Competition Makes All Great Again. Looks like it's by God's design. ^_^

kindkang2024 1y ago

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 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 useless for its actual usage here, isn’t it? ^^

matsemann 1y ago
Dynamic programming is for me one of the things that really scratched an itch and made me start liking programming. The invariant/inductions of composing smaller things into a bigger solution is so elegant. I do feel dynamic programming influences how I solve problems in my work. How, if you compose the problem correctly, it can never reach a fault state in a sense. Not sure if I'm able to explain what I mean, but for instance I recently refactored an old application at work that had lots of bugs, was hard to grasp and had loads of error checking code / asserts. However, by composing it a bit differently, modeling it properly, I could remove swaths of code / defensive programming because I with the help of the compilator now can guarantee the base cases holds etc. Edit: one a bit contrived example might be an Order. If you have one big model tracking the lifetime of an order, some fields will have to be null until they have a value. For instance a field sent_at_time. Then you have a function that generates an email to the customers, which uses that field. How do you handle that field possibly being null? Do you say "I know that at this point in time, this field is always set since the email is generated after sending" and tell the compiler to ignore the possibly null value? Or do you handle the possible null with some error handling / fallback value, that in practice is dead and cluttered code and will just confuse a future developer seeing it with questions like "how can this happen"? With the lessons from dynamic programming in mind, I think both are bad solutions. You want to be able to go from state n to n+1 with safety (order purchased, ordered sent, email sent). So model it in a way that the email sending code only ever can get an order in the correct previous state as input. Then if the assumption were to break in the future (maybe some orders are digital and the email is sent without the order having been physically sent), that breaking assumption will immediately be obvious in how the state/models are composed, and not in runtime when either the not-null-assert fails or the emails start having the fallback value.

nicknash 1y ago

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?

xandrius 1y ago
That sounds very smart :D
- amelius 1y ago
  But aren't the programs given access to the problem data _after_ the program has been compiled?
  - colechristensen 1y ago
    There are plenty of opportunities to precompute _everything_ for a certain class of problems.
  - fer 1y ago
    Sure, but the input might be bounded/finite, or the operations needed similarly constrained (e.g. trigonometry operations). Then you can offload lots of the computation to the compilation, sometimes all of it.
  - SkiFire13 1y ago
    Yeah, but they didn't precompute the solution for that specific program data, they precomputed the solution for all possible ones, and then selected the correct one when the program data was provided.
npsomaratna 1y ago
No, sorry. I vaguely remember compile time limits, but they were high enough (30 seconds, I think?) that I didn't bother worrying about them (at least, that's my memory).

mort96 1y ago

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?

sidewndr46 1y ago
As others have mentioned the term was chosen to be distinctive and attractive.
bazoom42 1y ago
According the article, the term “dynamic” was chosen because it has positive connotations.
- moffkalast 1y ago
  [flagged]
  - jagged-chisel 1y ago
    Two hard problems in computer science…
    - fragmede 1y ago
      1. Cache invalidation 2. Naming things 3. Off-by-one errors
      - lvncelot 1y ago
        0. Race conditions
        cluckindan 1y ago
        4: Threconcadiparaurrenllecy, lism.ng,
  - 1y ago

ncruces 1y ago

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.

mrits 1y ago

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.

Sesse__ 1y ago

For my first programming competition (the national ICPC prequalifier, in 2002), I asked my teammates (who I didn't know very well, we had just cobbled together a team) a couple of minutes before the contest what this dynamic programming thing was. One of them was “oh, it's only caching the output of a recursive function” (technically, that's memoization, but who cares). I ended up solving a problem using DP a couple of minutes before the deadline, which was enough to get us to 3rd and to ICPC. Fun times.

aljgz 1y ago

In the university, we had a team for ACM ICPC. We helped our professor organize a local competition, to encourage more people to practice. We participated in that competition, of course. One question would give you a few numbers no greater than 13, and you would output the number of ways to put N queens on the cheeseboard of those sizes. Not a difficult problem, but our first implementation, needed 2 minutes while time limit was 1 minute. We could optimize, but we decided to run it for all possible numbers, write a new program with just a switch-case. This was q perfectly legal move. We could see his face while judging our submission, his huge surprise when code ended in milliseconds, his look of admiration at us, the curiosity about the solution, and finally his reaction when he checked out our code. Priceless.

ivan_gammel 1y ago
Fun enough, in commercial software engineering your solution won’t raise eyebrows as something routine and expected, but an efficient algorithm could do.
- ape4 1y ago
  Its called https://en.wikipedia.org/wiki/Memoization https://en.wikipedia.org/wiki/Memoization
  - pvitz 1y ago
    More like "precomputed table" and "table lookup"...
  - marcosdumay 1y ago
    Memoization is the kind of dynamic programming the first post on the thread is talking about.
TheJoeMan 1y ago
Had a similar problem in a highschool comp. sci. class with a maze-following algorithm where you got points off for back-tracking. Turns out your code could pre-fetch the entire maze before making a move, which I think goes against the spirit of the exercise.

radicalbyte 1y ago

I had to laugh hard the first time I heard about it, I mean it's a really obvious technique if you've ever done low-level programming on limited machines as it's very close to something we used to do all the time - calculate result tables and use lookups which we built in to our code. Trades memory for CPU when it's worth it. Dynamic programming takes the same idea but does it at runtime.

bo1024 1y ago
To be fair, DP generally also involves recursion in some way. You could describe it as a lookup table where, to fill in later entries of the table, you need to use the earlier entries.

hinkley 1y ago

I found this video very helpful: https://m.youtube.com/watch?v=oBt53YbR9Kk https://m.youtube.com/watch?v=oBt53YbR9Kk Yes, it is 5 hours long. At least 4 of those are worth it. Many people confuse caching with DP. I’ve had that conversation too often. I think it’s down to the memoization examples people choose being too toy and just looking like caching. Caching is global shared state, whereas memoization can be scoped to the current calculation and still be useful. But they always skip over tabulation, which is where I believe DP distinguishes itself.

bjourne 1y ago
But dp is a form of caching, no? It sacrifices space by caching intermediate results to compute successive results. The only reason it is called dp is because the "inventor" (Iirc Bell) needed a cool name.
- hinkley 1y ago
  No, memoization is not caching. That’s a reductive understanding that causes no end of trouble. Caching is global shared state. It brings nearly every problem that global shared state brings with it. If you conflate the two you miss all of the advantages of DP and “just use caches”. Memoization in the scope of DP (some languages misuse the word in their APIs) is acknowledging that a problem is self recursive and eliminating the duplicate work by either inverting the problem or storing previously calculated values. These are usually call graph scoped. Nobody else sees the value. For instance in the case of solving Fibonacci with iteration, you need only remember the previous two values, which you store in registers. There is no table. There is no O(n) storage space. Again, tabulation is when the contrast becomes stark. You’re creating an array where the relationship between the values contains information that makes the calculations cheap.
  - bjourne 1y ago
    No definition of "caching" I know imply global shared state. Local private caches are commonplace.