This article will walk you through how to solve another classic DP problem: Longest Increasing Subsequence (LIS). To make it a bit more fun, we are going to pick another problem from the UVA¹ database: Strategic Defence Initiative². Read that problem first before continuing this article.

In short, the problem states that there are some enemy missiles heading your way and you are equiped with a missile system to intercept them. For every missile you launch, the next one can only be launched at a higher altitude than the previous one (because of a flaw in your missile system). …

This article will walk you through a problem called Cutting Sticks¹ from UVA (Universidad de Valladolid)’s problem set². Read the original problem before continuing this article.

We have a stick (wood) that needs to be cut:

The cuts must be done in certain parts of the stick. You must cut the stick in **all** marked places. For example, consider a stick of size 10 and 3 places marked in it (positions 2, 4 and 7) where the cuts must be made.

The cost to make a cut is the same as the size of the stick. For instance, if you…

Dynamic Programming (DP) is a generic programming technique that uses memorisation in order to solve problems that can be broken down into smaller problems of the same type.

Richard Bellman was the first to coin its name. He wanted to study these kind of problems back in the 1950s while he was in the US Air Force. The problem is that the Air Force at the time did not want to spend money funding mathematical research. To get around that, Bellman came up with a meaningless name (Dynamic Programming) so that he could continue working on it secretly as apparently…