Here’s something that might sound strange. Today, while playing the puzzle game “Mushroom Man” — a great throwback to old PC games like “Chip’s Challenge” — I noticed how similar one of the levels was to a solving a programming contest question. In level 113 “Don’t Drink the Water,” there is a large number of water tiles and only a limited amount of oxygen available to cross those tiles. At one point, I found myself on a spot where all paths left me exactly 1 oxygen short. Eventually, I needed to work backwards, counting the tiles to look for a solution. The shape of the level — a 10×10 grid with the goal in the corner — reminded me a lot of a dynamic programming solution where you would fill in a 2D integer array.
The origin of the term dynamic programming has very little to do with writing code. It was first coined by Richard Bellman in the 1950s, a time when computer programming was an esoteric activity practiced by so few people as to not even merit a name. Back then programming meant “planning,” and “dynamic programming” was conceived to optimally plan multistage processes.
Dynamic programming is about breaking a large problem into sub-problems, and using those sub-solutions to find the large solution. While you could write a DP solution recursively, it’s usually much more efficient to start with the smallest problem, and iteratively build up to the large one. A lot of the classic examples, such as the longest subsequence problem, can be solved by building a 2-dimensional table. For that reason, I like to think of DP algorithms as table-building.
This level is a great candidate for table-building because it has practically no obstacles and the few that exist can be ignored (the pink jellybeans can be pushed aside, and the purple teleporters only serve to force you along a certain path at the very start). It also doesn’t feature a lot of different items or dependencies, so it doesn’t require any backtracking (e.g. to find the best order to acquire items). Overall, it’s one of the easier levels.