# Dynamic Programming

Another Monday is upon us, and another batch of links is due. This week I’m going to focus on Dynamic Programming (or DP for short). The reason is that upcoming Project Euler problems are DP- and memoization heavy. Another reason is that DP problems are quite popular, so it’s definitely a good skill to have.

First up is a TopCoder Algorithm Tutorial, namely Dynamic Programming: From novice to advanced. This is a good “first look” at DP. It’s a bit heavy in the end, but that part can be skipped.

After you’ve read that, you should take a look at Bruce Merry‘s introduction to Dynamic programming. It’s got a really great step-by-step approach to solving a DP problem, which in my experience works quite well. Continue reading →

Posted by Bjarki Ágúst in Other, 5 comments

## Project Euler 82: Find the minimal path sum from the left column to the right column

In Problem 82 of Project Euler we are continuing to look at the same problem we considered in Problem 81. The problem reads

NOTE: This problem is a more challenging version of Problem 81.

The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994. 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331 Find the minimal path sum, in matrix.txt (right click and ‘Save Link/Target As…’), a 31K text file containing a 80 by 80 matrix, from the left column to the right column.

Posted by Kristian in Project Euler, 25 comments

## Project Euler 81: Find the minimal path sum from the top left to the bottom right by moving right and down.

Already from the headline of problem 81 of Project Euler it sounds familiar, so lets jump right in to it

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427. 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331 Find the minimal path sum, in matrix.txt (right click and ‘Save Link/Target As…’), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

Posted by Kristian in Project Euler, 20 comments

## Project Euler 77: What is the first value which can be written as the sum of primes in over five thousand different ways?

In problem 77 of Project Euler we are asked the following question

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

Posted by Kristian in Project Euler, 6 comments

## Project Euler 76: How many different ways can one hundred be written as a sum of at least two positive integers?

Problem 76 of Project Euler reads

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

Posted by Kristian in Project Euler, 13 comments

## Project Euler 67: Using an efficient algorithm find the maximal sum in the triangle?

Problem 67 of Project Euler feels a lot like cheating, since we have already solved the problem once in Problem 18

It is not even that I am clever to have seen the solution works for both problem, it is stated in the problem description which reads

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt, a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 299altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

Posted by Kristian in Project Euler, 11 comments

## Project Euler 31: Investigating combinations of English currency denominations

Problem 31 of Project Euler honestly baffled me for a while. That lasted until I realised that there is a simple brute force solution. But enough blabbering, the problem reads

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).It is possible to make £2 in the following way:

1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p

How many different ways can £2 be made using any number of coins?

Posted by Kristian in Project Euler, 32 comments

## Project Euler 18: Maximum Sum from Top to Bottom of the Triangle

The problem presented by Project Euler in Problem 18 is an optimization problem where you need to find the route through a triangle which maximizes the sum.  The problem reads

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2
4 6
8 5
9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

I will present you with two different solutions for this Project Euler problem. First a brute force solution, which the note state is possible for this problem, but not for Problem 67.  And latter I will present a Dynamic programming solution which can be reused for Problem 67. However, before addressing the algorithm part of the answer I will address the data representation, and how to read the data input.

At each level in the pyramid we always have two choices; we can go either left or right. Choosing left all he time will make us end up in the lower left corner, while choosing right will end us up in the lower right corner.

## Data Representation

I have chosen to store the input data in a 2-dimensional array (int[ , ] in C# syntax) for this problem, instead of an array of arrays (int[ ][ ] in C# syntax). I know that I could have saved almost half of the memory by doing it the other way, but I felt it was easier.

I have stored the problem in memory such in the following way

3 0 0 0
7 4 0 0
2 4 6 0
8 5 9 3

such that going right increases the index by one, and going left keeps the index, and the triangle is padded with zeros.

I wrote a small input function so I could read the problem data from a text file and store it in a 2-dimensional array. I will use the input reader for both solutions. The C# implementation of the input function looks like

```private int[,] readInput(string filename) {
string line;
string[] linePieces;
int lines = 0;

while ((line = r.ReadLine()) != null) {
lines++;
}

int[,]  inputTriangle = new int[lines, lines];
r.BaseStream.Seek(0, SeekOrigin.Begin);

int j = 0;
while ((line = r.ReadLine()) != null) {
linePieces = line.Split(' ');
for (int i = 0; i < linePieces.Length; i++) {
inputTriangle[j, i] = int.Parse(linePieces[i]);
}
j++;
}
r.Close();
return inputTriangle;
}
```

All it does is find the number of lines in the file, allocate an array that fits, and read in the data.

## Brute Force

When answering the problem with a brute force solution, it is pretty simple to go through the steps, we just need to try all combinations. Since we have a binary choice each time. We can iterate through all possibilities with a normal integer counter, and use the bits of the number to pick the direction left or right. While running through the path, we sum up the numbers and check if they are larger than the current maximum found.

I chose an implementation where I bitshift to find the left/right direction. It can be implemented in C# as

```string filename = Environment.GetFolderPath(Environment.SpecialFolder.DesktopDirectory) + "\\input.txt";

int posSolutions = (int)Math.Pow(2, inputTriangle.GetLength(0) - 1);
int largestSum = 0;
int tempSum, index;

for (int i = 0; i <= posSolutions; i++) {
tempSum = inputTriangle[0, 0];
index = 0;
for (int j = 0; j < inputTriangle.GetLength(0) - 1; j++) {         index = index + (i >> j & 1);
tempSum += inputTriangle[j + 1, index];
}
if (tempSum > largestSum) {
largestSum = tempSum;
}
}
```

It is a simple and easy approach, which works fine for this problem. The output of the code is

```The largest sum through the triangle is: 1074
Solution took 15 ms
```

## Dynamic Programming

The given problem is a classical example of dynamic programming, and it really works well for it. The methodology is a bit more complex than the brute force solution, but I will take a shot at explaining it anyway.
I will use the four line example to explain the idea throughout this section. Standing at the top of the triangle we have to choose between going left and right. In order to make the optimal choice (which maximizes the sum), we would have to know how large a sum we can get if we go either way. So in order to answer the question we would basically have to solve the two smaller problems which I have marked with blue and the orange in the figure to the right. We can break each of the sub-problems down in a similar way, and we can continue to do so until we reach a sub-problem at the bottom line consisting of only one number, then the question becomes trivial to answer, since the answer is the number it self. Once that question is answered we can move up one line, and answer the questions posed there with a solution which is a + max(b,c).

Once we know the answer to all 3 sub-problems on the next to last line, we can move up and answer the posed sub-problems by the same formula already applied. And we can continue to do so until we reach the original question of whether to go left or right.

### Optimal Sub-structure If we break down the problem into sub-problems we can see that breaking the orange sub-problem into two and breaking the blue sub-problem into two would yield us 4 sub-problems. However the sub-problem in the overlapping part is identical.  In this problem solving the sub-problem yields the same result no matter how we reached the it. This is fairly easy to see in this example. When a problem has this property it is said to have optimal sub-structure. Since we have a problem with optimal we only have to solve three sub-problem in the next to bottom line, and therefore the dynamic programming is effective.

It can be proven that the problem has an optimal sub-structure. However, I wont go into the details of that here, but leave that as an open end you can pick up and explore.

### Savings with Dynamic Programming

If we want to solve the small problem with brute force, we would need to test all 8 paths, each resulting in 3 additions, in total 24 additions.

If we use dynamic programming, the first iteration would require 3 maximum comparison operations and 3 additions. The next line would require 2 maximum comparison operations and 2 additions, and the first line would require one of each. So a total of 6 maximum comparison operations and 6 additions.

For small problems this saving is small if any at all, but for a problem with 15 lines, solving the first iteration would and brute forcing from there would reduce the number of brute force additions from 15*214 to 14*213 a saving of approximately 131000 fewer additions, at the cost of 15 additions and 15 maximum comparison operations. That is a pretty good saving.

### Dynamic Programming – The Algorithm

We can make a short-cut with the algorithm, as we don’t have to break the problem into sub-problems, but can start from the bottom and work the way up through the triangle until we reach the top and the algorithm spits out a number.

3
7 4
2 4 6
8 5 9 3

Applying the algorithm to the small problem we will need three iterations. The first iteration we apply the rule a + max(b,c) which creates a new triangle which looks as

3
7 4
10 13 15

Making the second iteration of the algorithm makes the triangle look

3
20 19

And if we run the algorithm once more, the triangle collapses to one number – 23 – which is the answer to the question.

My implementation of the algorithm in C# looks like

```string filename = Environment.GetFolderPath(Environment.SpecialFolder.DesktopDirectory) + "\\input.txt";
int lines = inputTriangle.GetLength(0);

for (int i = lines - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
inputTriangle[i, j] += Math.Max(inputTriangle[i+1,j], inputTriangle[i+1, j+1]);
}
}
```

The output of the algorithm is

```The largest sum through the triangle is: 1074
Solution took 3 ms
```

## Closing Remarks

For Problem 18 as we have solved here, the difference is very small. However, once we apply the algorithms one Problem 67, the different approaches will be a matter of getting the answer or not.

I have seen another solution using Dynamic Programming over at Functional fun, where he goes the other way through the triangle. I think mine is easier to understand, and ends up with one solution rather than a series of numbers you need to find the maximum of, but I will let you decide.

As usual I have uploaded the source code for you to play around with. Any comments, suggestions or improvements are very welcome; both for the code and for the explanation. I love to get feedback on how to improve my communication and problem solving skills.

Posted by Kristian in Project Euler, 33 comments

## Project Euler 15: Routes through a 20×20 grid

The problem description in Problem 15 of Project Euler contains a figure, which I wont copy, so go ahead an read the full description at the Project Euler site. The problem can be understood without it though. The problem reads

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20×20 grid?

My first question for many of the problems has been – Can it be brute forced? And my best answer to that is “probably”, but I cannot figure out how to generate all the routes. So instead I will give you two other approaches, which are both efficient. One is inspired by dynamic programming and the other gives an analytic solution using combinatorics. Continue reading →

Posted by Kristian in Project Euler, 40 comments