SUMTRIAN - implementing memoization

general
, , ,
1

I have spent many hours trying to solve the SUMTRIAN problem (http://www.codechef.com/problems/SUMTRIAN/) I know how my program works, I am implementing recursion, and I am doing my best to implement memoization (this is new for me). The code works perfectly fine for small triangles. However, every submission to CodeChef exceeds the time limit. Can anyone give me any pointers, please?

Thanks,

public class Main {

private static int[][] triangle = new int[0][0]; 
private static int[][] computedPaths = new int[0][0]; //for memoization

public static void main(String[] args){

	java.util.Scanner input = new java.util.Scanner(System.in);

	int cases = input.nextInt();

	int[] solutions = new int[cases];
	int solutionsIndex = 0;

	for(int i = 0; i < cases; i += 1){//for each triangle

		int lines = input.nextInt();
		triangle = new int[lines][lines];
		computedPaths = new int[lines][lines];

		int level = 1; //top of triangle is level 1 and level increases as works towards base

		for(int y = 0; y < lines; y += 1){
			for(int x = 0; x < level; x += 1){
				triangle[y][x] = input.nextInt();
			}
			level += 1;
		}

		//save outputs in array until all inputs are processed
		solutions[solutionsIndex] = findGreatestRouteValueRecursively(0,0);
		solutionsIndex += 1;
	}

	for(int i = 0; i < solutions.length; i += 1){
		System.out.println(solutions[i]);
	}

}//end main

public static int findGreatestRouteValueRecursively(int y, int x){
	if(y >= triangle.length)
		return 0;
	else if(computedPaths[y][x] == 0){
		int value1 = findGreatestRouteValueRecursively(y+1, x);
		int value2 = findGreatestRouteValueRecursively(y+1, x+1);
		computedPaths[y][x] = Math.max(value1, value2) + triangle[y][x];
	}
	return computedPaths[y][x];

}//end findGreatestRouteValueRecursively()
}
2

bump - any tips on how to memoize this would be greatly appreciated! the only code to rly look at is the findGreatestRouteValueRecursively at the bottom

3

Solved - for anyone curious, what made the difference was changing my input from Scanner to BufferedReader and InputStreamReader. Lesson learned :slight_smile:

Code below:
public class SumsInATriangle {

private static int[][] triangle = new int[0][0]; 
private static int[][] computedPaths = new int[0][0]; //for memoization

public static void main(String[] args) throws java.io.IOException{

	java.io.BufferedReader reader = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
	String[] in = reader.readLine().split(" ");
	
	int cases = Integer.parseInt(in[0]);

	int[] solutions = new int[cases];
	int solutionsIndex = 0;

	for(int i = 0; i < cases; i += 1){//for each triangle

		in = reader.readLine().split(" ");
		
		int lines = Integer.parseInt(in[0]);
		triangle = new int[lines][lines];
		computedPaths = new int[lines][lines];

		int level = 1; //top of triangle is level 1 and level increases as works towards base

		for(int y = 0; y < lines; y += 1){
			in = reader.readLine().split(" ");
			for(int x = 0; x < level; x += 1){
				triangle[y][x] = Integer.parseInt(in[x]);
			}
			level += 1;
		}

		//save outputs in array until all inputs are processed
		solutions[solutionsIndex] = findGreatestRouteValueRecursively(0,0);
		solutionsIndex += 1;
	}

	for(int i = 0; i < solutions.length; i += 1){
		System.out.println(solutions[i]);
	}

	//		int level = 1; //print triangle
	//		for(int y = 0; y < triangle[0].length; y += 1, level += 1){
	//			for(int x = 0; x < level; x += 1){
	//				System.out.print(triangle[y][x] + " ");
	//			}
	//			System.out.println();
	//		} 
}//end main

public static int findGreatestRouteValueRecursively(int y, int x){
	if(y >= triangle.length)
		return 0;
	else if(computedPaths[y][x] == 0){
		int value1 = findGreatestRouteValueRecursively(y+1, x);
		int value2 = findGreatestRouteValueRecursively(y+1, x+1);
		computedPaths[y][x] = Math.max(value1, value2) + triangle[y][x];
	}
	return computedPaths[y][x];

}//end findGreatestRouteValueRecursively()

}//end class