In this post I will explain how to solve the exercise Hexagonal Tiles [link], using the concept of Dynamic Programming.

This exercise is quite simple, and it’s a good start for those who don’t have familiarity with Dynamic Programming yet.

Click in the link below to see the post.

The concept of Dynamic Programming can be explained in several ways, and I will use one of them in here.

I will divide the exercise in **main problem**, and **sub-problem**:

**Main problem**is the goal problem, the one we want to know the answer.**Sub-problem**is a problem similar to the**main problem**. It’s not the goal problem, but its resolution will help to solve the**main problem**.

With this definition in mind, let’s see the exercise: we want to find out the number of different paths, from the tile number 0 (the one with the smiling face), and ending at the tile **N**.

Here the **main problem** is obvious: Number of paths, starting at the tile 0, and ending at the tile **N**.

But what about the **sub-problem**?

According to the definition, it will be similar to the **main problem**.

Let’s try this: Number of paths, starting at the tile **K**, and ending at the tile **N**.

It’s similar to the **main problem**, and since **K** is different from 0, it’s not the goal problem.

Ok, once the **main problem** and the **sub-problems** are defined, how is a **sub-problem** supposed to help in the resolution of the **main problem**, or even in the resolution of another **sub-problem**?

Let’s visualize the problem. If we are at the tile **K**, where can we walk?

Ok, if we are at the tile **K**, we have two paths: We can go to the tile **K**+1, and follow some path until the tile **N**; or we can go to the tile **K**+2, and follow some path until the tile **N**.

If, for instance, we go to the tile **K**+1. Now, where can we walk?

Notice the similarity?

All the **sub-problems** are equal, and the only thing that changes is the value of **K**. And the best: they are all related!

If we solve one, we are helping solving another, and that consequently leads us to the resolution of the **main problem**, once it’s similar to the **sub-problems**, as well as it’s related to them.

Let’s think about a formula: be “np” equal to “number of paths”, we have:

np[**K**] = np[**K**+1] + np[**K**+2].

To find out np[**K**], we need to find out np[**K**+1] and np[**K**+2]. To find out np[**K**+1], we need to find out np[**K**+2] and np[**K**+3]. When does it end?

I present you something called **base case**.

**Base case** is a particular **sub-problem** so ridiculously easy that we don’t need other **sub-problems** to solve it. You can solve it by yourself.

For example, if we are at the tile **N**, how many paths are there until the tile **N**? Well, just 1, because we are already there.

And if we are at the tile **N**-1, how many paths are there until the tile **N**? Well, just 1, because you just have to walk ahead.

Now we just have to solve the **sub-problems**, from right to left, and we will get to the **main problem**. Here is the code in C++:

// number of tiles int N; scanf("%d", &N); // array with the answer to the sub-problems int np[N+1]; // base cases np[N] = 1; np[N-1] = 1; // sub-problems for(int K=N-2; K>=0; K--) { np[K] = np[K+1] + np[K+2]; } // the main problem is solved when K is equal to 0, in the loop above // answer printf("%d\n", np[0]);

Any doubt, suggestion or review, let me know below.