• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

dynamic programming: i rephrase the question

 
Randall Twede
Ranch Hand
Posts: 4469
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4469
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic