Hello!
Let's say we have a matrix of size N*N filled with arbitrary positive
integers. Now, let's say we would like to move from the upper left
point ([0,0]) to the lower right point [N-1,N-1] moving only down OR
right, so that a path with the minimum sum of elements is created. Ex .
When n= 3
On 11/6/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
Now I wrote a recursive function, that calculates the minimal path sum
for a matrix N=80 :
=
unsigned long long sum(int i, int j) {
=
Now, the code works pretty fast for small matrices,
123
456
789
the minimal path sum is 1 + 2 +3 + 6 + 9 = 21
Looks like a shortest path problem in a weighted graph. Represent the
numbers as the weights of edges in the graph. Each node will have two
child nodes - one going right and one going down. Once you construct a
graph, apply
Thanks for the reply :-)
I've never worked with graphs or something, and I'm very interested in
a non-graph solution. (working only on the integer array)
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm
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
Its called memoization.. its a standard technique... http://en.wikipedia.org/wiki/Memoization-VijjuOn 11/6/06,
[EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
Nice hint indeed! The code finish in 0.02s taking in account that somesums repeats! Thanks for the hint really! I feel so dumb to not
Call for Papers
and
Call for Session Proposals
The 2007 World Congress in Computer Science,
Computer Engineering, and Applied Computing
WORLDCOMP'07
(composed of 24 Joint Conferences)
June
Thisseems to beone 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
Check out:
http://en.wikipedia.org/wiki/UUID
Arunachalam wrote:
Look at one way hashing algorithms. Which can map a password to some byte
keys.
I think MD5 will solve your purpose. But collisions are possible in MD5.
http://en.wikipedia.org/wiki/MD5
regards
Arunachalam.
On 11/2/06,
