Win a copy of The Java Performance Companion this week in the Performance forum!

# dynamic programming: i rephrase the question

Randall Twede
Ranch Hand
Posts: 4439
3
i am trying to solve Euler81. it is very similar to Euler67. the only differences is 67 is a triangle and 81 is a square, and 67 wants maximum while 81 wants minimum.
i get the correct answer to 67, but for 81 i get 409646 when the correct answer is apparently 427337.
i thought i was using the same approach for both.
67

81

Randall Twede
Ranch Hand
Posts: 4439
3
solved it finally.
for(int j = i - 1; j >= 0; j--)
{
data[i][j] = data[i][j] + Math.min(data[i + 1][j], data[j + 1][i]);
data[j][i] = data[j][i] + Math.min(data[i + 1][j], data[j + 1][i]);
}
should have been
for(int j = i - 1; j >= 0; j--)
{
data[i][j] = data[i][j] + Math.min(data[i + 1][j], data[i][j + 1]);
data[j][i] = data[j][i] + Math.min(data[j + 1][i], data[j][i + 1]);
}
as with all the dynamic programming solutions i have seen so far it is quite simple, elegant, and fast.