Project Euler: 15 Lattice Paths

We have a grid of size \(20 \times 20\). We can reach the last step in 40 exactly steps. 20 of these steps must be down steps and the other 20 must be right steps. So we have a sequence of 40 steps total and we want to find all possible sequences of these steps. Suppose we first chose the down steps in the configuration below

So steps 1,3,4,7,8 … all are down steps. Then, automatically we know that the rest of the steps are just right steps. So once we determine the right steps, we’re done. The remaining steps will be down steps. So we’re only choosing 20 of the 40 steps. The number of ways to choose 20 steps out of 40 is given by the binomial coefficient.

A Dynamic Programming Solution

Another way to do this problem is with dynamic programming. Why do it this way? maybe just to practice? Suppose we’re at very last step. We could have come from the step above or the step to the left. Let ways\([i][j]\) be a matrix representing the numbers. So the number of the ways to generate the sequence of 40 steps is the sum of all ways if came from a step above plus all the ways if we came from a step on the left. Therefore, we naturally have a recurrence that we can implement below

unsigned long long ways[25][25];
memset(ways, 0, sizeof(ways));
ways[0][0] = 0;
ways[1][0] = 1;
ways[0][1] = 0;
for (int i = 1; i < 25; i++) {
    for (int j = 1; j < 25; j++) {
        ways[i][j] = ways[i-1][j] + ways[i][j-1];
    }
}
printf("reach(21,21) in %llu steps\n", ways[21][21]);

References

Project Euler - 16