Maximum path sum I
Problem 18
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.
Find the maximum total from top to bottom of the triangle below:
(https://projecteuler.net/problem=18)
3
7 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.7 4
2 4 6
8 5 9 3
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
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)
Problem 18 is awesome. It's simply amazing.
Personally, I found out dynamic programming while solving this problem, and it is one of the most powerful algorithms that I've ever learned.
As my brute force method took more than 5 minutes on the first attempt, the drastic improvement of efficiency down to 3 milli-second was astonishing advancement and was done solely by dynamic programming.
(Note that the solution will be same for Problem 67).
Anytime there is a large set of data, we are going to use read-file method to store the data.
private static int[][] triangle = read(); public static int[][] read() { int[][] text = new int[15][]; File file = new File(text018); try (BufferedReader br = new BufferedReader(new FileReader(file))) { String line; for (int i=0; (line = br.readLine()) != null; i++) { String[] temp = line.split(" "); text[i] = new int[i+1]; for (int j=0; j <= i; j++) text[i][j] = Integer.parseInt(temp[j]); } } catch (IOException e) { System.err.println(e); } return text; }
Instead of starting from the top and coming downward, I will start from the bottom and go upward.
Let's look at the bottom-left region, where a triplet of 63, 04, and 62 are located.
63
04 62
I will call 63 the parent number and 04 and 62 the daughter numbers.
63
04 62
We are going to modify our pyramid by adding the larger daughter number to the parent number.
63
04 62
62 is greater than 04, so I will add the number to the top.
125
04 62
If we do the same thing for the second pair, then:
66
62 98
164
62 98
We are going to do the same thing for all the pairs in the first floor, and then we will have the second floor with the greatest possible values of sums.
After finishing the second floor, then we will step up and select two pairs from the second floor and form the greatest possible values of sums in the third floor, and so on.
And because this is repetitive process, we can tell the program just once how to process the numbers, and after that computer will just follow through the logic until it reaches the last floor, or the top number, which will then become the largest possible sum of the adjacent numbers.
We call this dynamic programming.
Here is the implementation of the logic:
for (int i=triangle.length-1; i >= 1; i--) { for (int j=0; j < i; j++) { triangle[i-1][j] += Math.max(triangle[i][j], triangle[i][j+1]); } } System.out.println(triangle[0][0]);
Answer is 1074
Execution time is 3.042578 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem018.java
