Question
The method below is supposed to count the number of paths.We want to count the number of possible paths to move from row 1, column 1 to row N, column N in a two-dimensional grid. Steps are restricted to going up or to the right, but not diagonally.
Something is wrong with the method below as stated in the text book. What is wrong with the method?
static int numPaths(int row, int col, int n) { if (row == n) return 1; else if (col == n) return (numPaths + 1); else return (numPaths(row + 1, col) * numPaths(row, col + 1)); }
Explanation / Answer
/** * Compute the number of paths from (1,1) to (n,n). N is given on * the command line. Is not very friendly about errors. Uses * a two-dimensional array to keep track of previously computed * values. * SOLUTION public class NewNumPaths { /** The number of recursive calls. */ protected long calls = 0; /** * A two dimensional array to keep track of the number of paths * from (x,y) to (n,n). pathsFrom[x-1][y-1] gives the number * of paths from (x,y) to (n,n). If it is not yet set at a * particular position, it has the value -1 in that position. */ protected long[][] pathsFrom; /** * Compute the number of paths from (row,col) to (n,n). * (row,col) should not be (n,n). */ public long numPaths(int row, int col, int n) { calls++; // Base cases: if ((row == n) || (col == n)) { return 1; } else { // Make sure that the array is initialized. if (pathsFrom == null) { pathsFrom = new long[n][n]; for (int i = 0; i