programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# dynamic programming: i rephrase the question

Randall Twede
Ranch Hand
Posts: 4696
8
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: 4696
8
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.

 It is sorta covered in the JavaRanch Style Guide.