Posts Tagged with "Dynamic Programming"

mondaylinks2

Monday links

Monday, August 13, 2012

5 Comments

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.Take a look inside for more.

Continue reading...
large-matrix-blu-ray7

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

Saturday, February 4, 2012

21 Comments

In Problem 82 of Project Euler we are continuing to look at the same problem we considered in Problem 81. The problem readsFind the minimal path sum, in a 80 by 80 matrix, from the left column to the right column.The big difference here is that we are now allowed to move up as well as down, and that means we can't make as small sub problems as before. However, since we are not allowed to move left we can still slice the matrix into columns and solve smaller problems that way. So dynamic programming is still a viable solution.

Continue reading...
large-matrix-blu-ray7

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

Saturday, January 28, 2012

14 Comments

Already from the headline of problem 81 of Project Euler it sounds familiar, so lets jump right in to it Find the minimal path sum in a 80 by 80 matrix, from the top left to the bottom right by only moving right and down. This is one of the most classic examples of problems which can be solved using dynamic programming. We have already solved Problem 15 where we used a sort of dynamic programming approach to traverse a grid to find the number of paths through the grid. We also solved problem 18 with dynamic programming to find the minimum path through a triangle.

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

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

Saturday, December 31, 2011

4 Comments

In problem 77 of Project Euler we are asked the following question What is the first value which can be written as the sum of primes in over five thousand different ways?This question is actually very similar to the problem we just solved in Problem 76 except that it asks us to find a number with a certain property, instead of asking what property a certain number have.I took the easy solution and modified the solution for problem 76, to search for the first number with a solution larger than 5000. In order to do that we need to make two changes.

Continue reading...
100

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

Saturday, December 24, 2011

8 Comments

Problem 76 of Project Euler readsHow many different ways can one hundred be written as a sum of at least two positive integers?It is one of the shortest descriptions I have read for a long time and it will be one of the shortest solutions I have written for a short while. When I solved this I thought I was really clever to realise we could reuse an old solution for this. But apparantly the majority of the 9000+ other users who have solved it realised the same thing.

Continue reading...
Project Euler 67: Using an efficient algorithm find the maximal sum in the triangle?

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

Wednesday, October 26, 2011

10 Comments

Problem 67 of Project Euler feels a lot like cheating, since we have already solved the problem once in Problem 18It 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 Find the maximum total from top to bottom in triangle.tx, a 15K text file containing a triangle with one-hundred rows.However, I thought I would write a short post on it just because otherwise I feel I have a hole in the series. So in Problem 18 I described a solution based on dynamic programming which is the thing we need to use here.

Continue reading...

Project Euler 31: Investigating combinations of English currency denominations

Saturday, March 12, 2011

21 Comments

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 How many different ways can £2 be made using any number of coins?As mentioned before I have found a brute force solution which is a completely viable way to go, and I have found a dynamic programming solution. For the problem size of 200p the solutions are equally fast, but for larger problems the dynamic programming solution is significantly faster.

Continue reading...

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

Wednesday, December 29, 2010

19 Comments

problem 18 of Project Euler reads By starting at the top of the triangle below and moving to adjacent numbers on the row below. Find the maximum total from top to bottom of the triangle below.This problem is a classical dynamic programming problem, so in the post I have solved it using both a brute force approach which is more than fast enough for the posed problem, as well as a dynamic programming approach.

Continue reading...

Project Euler 15: Routes through a 20×20 grid

Wednesday, December 15, 2010

17 Comments

Given problem 15 of Project Euler which reads How many routes are there through a 20x20 grid?I propose two different solution approaches. One which is heavily inspired by dynamic programming and one which uses combinatorics. Both solutions are efficient and scale really well.

Continue reading...