This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Java in General and the fly likes dynamic programming: i rephrase the question Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "dynamic programming: i rephrase the question" Watch "dynamic programming: i rephrase the question" New topic
Author

dynamic programming: i rephrase the question

Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

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


SCJP
Visit my download page
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: dynamic programming: i rephrase the question
 
Similar Threads
anyone good at dynamic programming?
reading strings from a file
Part of program not printing output
idea for this pls?!
Merging rows with same ID together with dynamic headers with CSV