# dynamic programming: i rephrase the question

posted 3 years ago

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

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

SCJP

Visit my download page

posted 3 years ago

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.

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.

SCJP

Visit my download page