Dynamic programming approach in action

This topic will show you how to apply the dynamic programming approach to find a solution for the classic grid walk problem. This problem or, more precisely, this type of problem, requires counting all possible ways to walk across a grid of an arbitrary size subject to certain conditions. The techniques you will learn in this topic will grant you hands-on experience in solving similar dynamic programming problems.

Problem description

Consider a rectangular grid of a certain width and height. The starting point is in the top left corner of the grid and the destination point is in the bottom right corner. The goal is to find all possible paths to walk across the grid provided that you may move either to the right or down from the cell you are currently in:

Let's think about the problem and try to find a possible solution step by step. The first thing to keep in mind is that from any given cell you can move in exactly two directions. Second, you can never re-visit any already visited cell, which means you don't have to worry about tracking the cells you have visited. Another important thing is that whenever you take a step you find yourself in a situation very similar to the one you had in the previous step. You will have a grid to walk across but its height or width will be lesser by one than in the previous step, depending on which direction you chose.

This means that you have the same problem as at the beginning of the walk but with different starting conditions and this new problem is a subset of the initial problem. So you can try to solve the sub-problems first and then somehow combine the solutions of all sub-problems to get the solution of the whole problem. Dynamic programming suggests solving each sub-problem only once and reusing the solution but now we are going to divide the problem into sub-problems and deal with the reusability later.

Dividing the problem

Since each sub-problem is of the same type as the initial problem, you can try applying recursion.

In the first approximation, the solution is going to be a function that accepts a grid and returns the number of paths found. First, you should decide how you want to represent the grid. Are you going to use a class or an array, or some other data structure? To make a decision, let's explore how to track the current position in the grid. Take a closer look at this image:

Do you really need to track your coordinates? Probably no. You can pretend that when you take each step you create a new grid with one side lesser by 1 than the previous grid. This leads to a solution where you may pass only the grid's width and height as the arguments:

public class Main {
    public static void main(String[] args) {
        // var paths = ...
    }

    static long countPaths(int width, int height) {
        // TODO recursion
    }
}

Let's figure out the base conditions for this recursion. When can you say that you've reached the finish point? When you hit the bottom right cell, you have nowhere to go because the available grid is the size of one cell:

In this case, countPaths should return 1 because you reached the finish and found a new path.

static long countPaths(int width, int height) {
    // if grid size is 1 by 1, we found a path
    if (width == 1 && height == 1) {
        return 1;
    }

    // TODO recursion
}

What if you reach a border row or column in the grid? If you take a step outside the grid, you won't reach the finish anymore. So you should either avoid exiting the grid or detect that you have exited it and discontinue the walk. For example, if the current width is 1 you should not go to the right and if the current height is 1 you should not go downwards:

Another, and maybe an easier way is to detect a situation when the current position is outside the grid, that is when either width or height is less than 1. If you detect that you stepped out of the grid, countPaths should return 0. This means that you took a path and failed to reach the finish:

static long countPaths(int width, int height) {
    // if width or height is 0, we are outside the grid
    if (width == 0 || height == 0) {
        return 0;
    }

    // if grid size is 1 by 1, we found a path
    if (width == 1 && height == 1) {
        return 1;
    }

    // TODO implement me with recursion
}

So far, only the recursion part remains. As you may choose only two directions, you need to sum the number of paths found in both directions and return that number:

static long countPaths(int width, int height) {
    // if width or height is 0, we are outside the grid
    if (width == 0 || height == 0) {
        return 0;
    }

    // if grid size is 1 by 1, we found a path
    if (width == 1 && height == 1) {
        return 1;
    }

    // if we go right, width decreases
    var rightwards = countPaths(width - 1, height);

    // if we go down, height decreases
    var downwards = countPaths(width, height - 1);

    return rightwards + downwards;
}

Did we miss anything? Probably not. Let's test this solution on a few small grids where we can count all possible paths manually:

public class Main {
    public static void main(String[] args) {
        var paths = countPaths(2, 2);
        System.out.println(paths);

        paths = countPaths(2, 3);
        System.out.println(paths);

        paths = countPaths(3, 3);
        System.out.println(paths);
    }

    static long countPaths(int width, int height) {
        // if width or height is 0, we are outside the grid
        if (width == 0 || height == 0) {
            return 0;
        }

        // if grid size is 1 by 1, we found a path
        if (width == 1 && height == 1) {
            return 1;
        }

        // if we go right, width decreases
        var rightwards = countPaths(width - 1, height);

        // if we go down, height decreases
        var downwards = countPaths(width, height - 1);

        return rightwards + downwards;
    }
}

Here is the output:

2
3
6

It worked!

Are you excited to count the number of paths for a really big grid? Say, 30x40? Let's run it and see if we are going to have an overflow. Seems like the program takes too long to run. Let's investigate the reasons and find a solution.

Bad performance

First, it is worth measuring the execution time. For this, let's refactor the code and wrap the path counting method with a method that calculates its execution time:

import java.time.Duration;
import java.time.Instant;
import java.util.function.Supplier;

public class Main {

    // main and countPaths methods

    static void runner(Supplier<?> pathCounter) {
        var start = Instant.now();
        var paths = pathCounter.get();
        var duration = Duration.between(start, Instant.now());
    
        var message = "%-35s in %ds %dms".formatted(
                paths, duration.toSecondsPart(), duration.toMillisPart()
        );
        System.out.println(message);
    }
}

And then check the execution time for a series of grid sizes:

public class Main {
    public static void main(String[] args) {
        for (int i = 11; i < 18; i++) {
            final int size = i;
            runner(() -> countPaths(size, size));
        }
    }

    // countPaths and runner methods
}

The execution time is growing extremely fast:

184756                             in 0s 2ms
705432                             in 0s 5ms
2704156                            in 0s 21ms
10400600                           in 0s 77ms
40116600                           in 0s 316ms
155117520                          in 1s 123ms
601080390                          in 4s 298ms

Why is it happening? To understand it, take a look at the execution of the recursive method for a small grid (3 x 2):

The numbers in the rectangles indicate the current grid size, the words down and right show the chosen direction and the numbers near the lines are the values returned by countPaths for the given grid size.

1. The execution starts when the grid is 3 x 2.

2. If the downward path is taken, the grid size becomes 3 x 1.

3. If the downward path is taken again, we step out of the grid (3 x 0). At this point, countPaths returns 0.

4. If at step 3 we choose another direction, the grid size becomes equal to 2 x 1.

5. If the right path is taken, we reach the finish and countPaths returns 1.

6. If the downwards path is chosen at step 5, we again step outside the grid and countPaths returns 0.

7. At this point, the method at step 5 receives two results from invoked countPaths, 1 and 0, and returns their sum to the method invoked at step 2 which in its turn adds the value produced at step 3 and returns the sum to the caller method.

The same applies to the right part of the execution tree. If you look closely, you will notice that there are steps with the same input arguments and the same returned values. This is where countPaths does some extra work, and the higher the tree, the more extra work happens. It's time to find a way to solve each sub-problem only once and reuse the solutions.

Memoization

Memoization is a technique that helps reuse solutions calculated for sub-problems. You can associate the current position in the grid with the found number of paths available for that position and store such information in an appropriate data structure. Let's write a new version of countPaths that uses memoization:

import java.math.BigInteger;
import java.util.Map;

// This version is suitable for big grids 
// so the return type is BigInteger to avoid overflow
static BigInteger countPathsMemo(int width, int height, Map<String, BigInteger> memo) {
    // if width or height is 0, we are outside the grid
    if (width == 0 || height == 0) {
        return BigInteger.ZERO;
    }

    // if grid size is 1 by 1, we found a path
    if (width == 1 && height == 1) {
        return BigInteger.ONE;
    }

    // creating a key representing the current input
    var key = "w" + width + "h" + height;

    // if the map already contains the key, return the associated value
    if (memo.containsKey(key)) {
       return memo.get(key);
    }

    // if we go right, width decreases
    var rightwards = countPathsMemo(width - 1, height, memo);

    // if we go down, height decreases
    var downwards = countPathsMemo(width, height - 1, memo);

    var paths = rightwards.add(downwards);

    // save the calculated number of paths in the map
    memo.put(key, paths);

    return paths;
}

Let's run the performance test for the new method:

import java.math.BigInteger;
import java.time.Duration;
import java.time.Instant;
import java.util.HashMap;
import java.util.Map;
import java.util.function.Supplier;

public class Main {
    public static void main(String[] args) {
        for (int i = 10; i <= 60; i += 10) {
            final int size = i;
            runner(() -> countPathsMemo(size, size, new HashMap<>()));
        }
    }

    // countPaths, countPathsMemo and runner methods
}

You will see that memoization improves its performance tremendously:

48620                               in 0s 3ms
35345263800                         in 0s 1ms
30067266499541040                   in 0s 2ms
27217014869199032015600             in 0s 1ms
25477612258980856902730428600       in 0s 1ms
24356699707654619143838606602026720 in 0s 1ms

For a grid as big as 60 x 60, the execution time is a few milliseconds, and even a 300 x 300 grid takes a fraction of a second to calculate.

Conclusion

In this topic, we applied dynamic programming to solve a grid walk problem. We took a close look at the problem's description to get a better comprehension and find a suitable solution. In the process, we found a pitfall associated with recursion and successfully bypassed it using the memoization technique. The use of appropriate data structures and the standard library helped with implementing a reliable solution. We hope that this topic will help you efficiently deal with similar tasks and real-life problems!