Programming Contest: Pascal
Description
Given an n x n game board, travel along any legitimate path from the upper left corner to the lower right corner of the board. The integer in any square dictates how large a step away from that location must be. The solution below uses memoization in recursion, there by making the solution dynamic, in a sense.
[ complete description ] [ pascal.java ]
Sample Input
4
2331
1213
1231
3110
4
3332
1213
1232
2120
5
11101
01111
11111
11101
11101
-1
Sample Output
3
0
7
Solution
public static long solve(int x, int y)
{
// there is exactly 1 way from the end point to itself
if(x == n - 1 && y == n - 1)
return 1;
// there are exactly 0 ways if you are off the board
if(x < 0 || y < 0 || x >= n || y >= n)
return 0;
// there are exactly 0 ways if you cannot jump
if(board[y][x] == 0)
return 0;
// if answer has already been found
if(done[y][x])
return ans[y][x];
// otherwise, you can choose to jump down or jump right, the answer is the sum of the two.
// note that each time, you are reducing the number of paths to the result
ans[y][x] = solve(x + board[y][x], y) + solve(x, y + board[y][x]);
done[y][x] = true;
return ans[y][x];
}