UVa - 196 - Spreadsheet

Link to the problem on UVa Online Judge
Link to the pdf version

In my opinion this is a classic Dynamic Programming problem which can be solved with a top-down approach. The most important part of this problem is that it explicitly states that there are no cyclic dependencies between cells, a key part in a dynamic programming solution.
The fact that we can solve a problem with a top-down approach shows that there are no cyclic dependencies between subproblems. Actually it's a DAG, Directed Acyclic Graph, in which larger subproblems are dependent on smaller subproblems.
The tricky part which requires more attention is parsing input and calculating row number and column number correctly.

	private static int convertToColumn(String s) {
	int result = 0;
	int p26 = 1;
	for (int i = s.length() - 1; i >= 0; i--) {
	result += p26 * (s.charAt(i) - 'A' + 1);
	p26 *= 26;
	}
	return result - 1;
	}

view raw convertToColumn.java hosted with ❤ by GitHub

This is my code for converting a string like A, AAB, AZ ... to column number.
The rest is a simple function which memoizes the answer to each cell, if it has been calculated before, it doesn't calculate it again and only returns the result.

	private static int calc(int i, int j) {
	if (mat[i][j] != -1) return mat[i][j];
	if (input[i][j].charAt(0) != '=') {
	mat[i][j] = Integer.valueOf(input[i][j]);
	return mat[i][j];
	}
	String[] all = input[i][j].split("[=+ ]");
	mat[i][j] = 0;
	for (String s : all) {
	if (s.length() > 0) {
	int firstDigit = indexOfFirstDigit(s);
	int colIndex = convertToColumn(s.substring(0, firstDigit));
	int rowIndex = Integer.parseInt(s.substring(firstDigit)) - 1;
	mat[i][j] += calc(rowIndex, colIndex);
	}
	}
	return mat[i][j];
	}

view raw calc.java hosted with ❤ by GitHub