[algogeeks] Re: Minimal path sum in a matrix (optimizing the algorithm)

Mon, 06 Nov 2006 15:17:36 -0800

This seems to be one of the Project Euler, www.mathschallenge.net problem, and this is probably the simplest one when you can solve it using memoization because the progression is only going to RIGHT or DOWN.
 
Later, you'll find the same problem with more "directions" ... it can go LEFT or RIGHT, UP or DOWN.  This is where the Dijkstra (or other shortest path algorithm) will help.
 
-Lego
 
On 11/6/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:

Nice hint indeed! The code finish in 0.02s taking in account that some
sums repeats! Thanks for the hint really! I feel so dumb to not think
about that before :-(

Anyway, the renewed function looks like :

=========================
unsigned cache[80][80] = {0};

#define CACHED(i,j)\
   if (!cache[i][j])\
       cache[i][j] = sum(i,j);

unsigned sum(int i, int j) {

   if (i == 79 && j == 79) {
       return matrix[i][j];

   } else if (j == 79 && i != 79) {
       CACHED(i+1,j);
       return matrix[i][j] + cache[i+1][j];
   } else if (i == 79 && j != 79) {
       CACHED(i, j+1);
       return matrix[i][j] + cache[i][j+1];
   }
   CACHED(i,j+1);
   CACHED(i+1,j);

   if (cache[i+1][j] > cache[i][j+1])
       return matrix[i][j] + cache[i][j+1];
   else
       return matrix[i][j] + cache[i+1][j];
}
=========================

thank you very much!



--~--~---------~--~----~------------~-------~--~----~
 You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to