Saturday, November 20, 2010

Memoized "Triangle" Problem

Write a 'memoized' recursive solution to the "Triangle" problem.  Assume that the data consists of a number of rows followed by the numbers for the triangle, from top to bottom.  Write a main method which reads the data and calls the recursive function which returns the highest sum obtained on a path from the apex to the base of the triangle.

int highestSum(int i, int j)
int left, right;
if (M[i , j] != -1) return M[i, j];
left = highestSum(i+1, j);
right = highestSum(i+1, j+1);
if (left > right)
M[i, j] = tri[i, j] + left;
M[i, j] = tri[i, j] + right;
return M[i, j];

No comments:

Post a Comment