Problem with Project Euler 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.

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

this is my code but it gives 21 instead of 23 what is wrong in the code thanks

Code :

public static void main(String[] args) {
List<List<Integer>> twoDim = new ArrayList<List<Integer>>();
int tempSum;
int temp ;
String[] inputLines = {"3","7 4","2 4 6","8 5 9 3"};
for (String line : inputLines) {
List<Integer> row = new ArrayList<Integer>();
Scanner s = new Scanner(line);
while (s.hasNextInt())
row.add(s.nextInt());
twoDim.add(row);
}
int lines = twoDim.size();
for (int i = lines-2 ; i >= 0; i--) {
for (int j = 0; j <= i; j++)
{
twoDim.get(i).add(j,twoDim.get(i).get(j)+Math.max(twoDim.get(i+1).get(j),twoDim.get(i+1).get(j+1)));
}
}
System.out.println(twoDim.get(0).get(0));
}

Re: Problem with Project Euler problem 18

While your approach may be clever - then again, maybe TOO clever - it is not easy to understand or troubleshoot. I suggest you simplify the part of your program that chooses which value of the next row to add to the total so that you can add test lines to see what is going wrong. Think about how you'd do it in your head or with pencil and paper and code that.

Re: Problem with Project Euler problem 18

Choosing the maximum adjacent value is not guaranteed to give the maximum sum from top to bottom (as demonstrated here).

Here's a more obvious example:

1

1 1

2 1 1

1 1 8 9

Your approach will choose 1 + 1 + 2 + 1, but the best approach is 1 + 1 + 1 + 9.

If you want to solve this problem the "lazy way", you can use a brute force solver and try every path. As the problem hint suggests, this will work here, but not on problem 67.

There's a more efficient solution, though (as the problem suggested). As a hint, think about the problem going backwards.