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.

Solution

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;

else

M[i, j] = tri[i, j] + right;

return M[i, j];

}

Solution

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;

else

M[i, j] = tri[i, j] + right;

return M[i, j];

}

## No comments:

## Post a Comment