Computer Algorithms 3

Today I would like to discuss an algorithm I have been working closely with for a while now, called dynamic programming. The idea of the topic is to use information that you have already calculated to reduce the number of computations your program has to do, and this method often works by using recursion.

As an example, (this problem is from CSES) imagine you have a rectangle, with side lengths  that are positive integers. You are allowed to split the rectangle into 2 pieces that preserves the rectangular shape of both pieces, and such that both rectangles have side lengths that are positive integers. You can also split any rectangle that is the result of a split. Your goal is to output the minimum number of such splits that leaves the remaining rectangles to also be squares.

At first look, this problem can seem daunting, but dynamic programming provides an elegant solution. Instead of trying every possible split and combination of splits, we can try to solve for the smallest inputs. We know that every square is automatically going to yield an answer of zero, so every time we can ignore calculating those dimensions. But what about everything else? Let’s start simple, with a 1 by 2 rectangle. This rectangle can only be cut once, into two 1 by 1 squares, thus the answer for a 1 by 2 rectangle is 1. What about a 1 by 3 rectangle? Well we could cut it into a 1 by 2 and 1 by 1 square, then that 1 by 2 into two 1 by 1 squares, but now that we know the minimum splits for a 1 by 2 rectangle is 1, then we don’t have to calculate how many splits to make the 1 by 2 squares. Then we can just add the number of cuts it takes to make the 1 by 2 a combination of squares, the number of cuts for the other shape (which is a 1 by 1 so zero), and 1, because it took us one cut to get to this situation, and this sum is the answer. This principle can apply to any rectangle with one of its side lengths as 1. But what happens when we complicate things? Let’s look at a 2 by 3 rectangle. You can split it into a 1 by 3 and 1 by 3, or you can split it the other way into a 1 by 2 and 2 by 2. But wait, we already know how many cuts it will take for us to get a 1 by 3 to squares, and a 1 by 2 to squares. We can simply take the minimum of cutting every possible way, which takes very little computational time compared to trying every possible cut and combination, which would repeat a lot of computing. Thus, this is our answer: work from small rectangles, running this method, until we reach the desired dimensions that the input asks for.

This method of solving problems varies so much that it’s not really an algorithm like many others; rather, it’s more of a method that cleverly avoids repeating computation. Hopefully you enjoyed reading about it!