Given an m by n grid, how many ways are there to get from the bottom left corner to the top right corner? You may only move right or up.
This is a type of problem I commonly encountered in middle school. There are two ways to solve it. One way is to notice that you must move up m times and right n times, and to find the number of permutations of those moves.
Another way, and the one I always preferred, is at each point to write down the number of paths to that particular point. To do this, we only need to know what numbers directly below and to the left. So we can start at the bottom left, and flood-fill the whole grid.
The advantage of this method, is that it can be easily generalized. Points you’re not allowed to go to? No problem. Diagonal paths? No problem.
Today, I realized that if you generalize this to the maximum extent, you get dynamic programming. Which is interesting, because bright elementary school students immediately find the solution to the grid problem very intuitive, and once they see it, they never forget it. In contrast, smart university students have been known to take a while to “get” dynamic programming.
