Counting paths in an n-dimensional grid that stay within the boundaries

Problem Statement


You are situated in an N dimensional grid at position (x1, x2, …, xN).
The dimensions of the grid are (D1, D2, …, DN). In one step, you can
walk one step ahead or behind in any one of the N dimensions. (So
there are always 2×N possible different moves). In how many ways can
you take M steps such that you do not leave the grid at any point? You
leave the grid if at any point xi, either xi ≤ 0 or xi > Di.

Input Format


The first line contains the number of test cases T. T test cases
follow. For each test case, the first line contains N and M, the
second line contains x1, x2, …, xN and the 3rd line contains D1, D2, …, DN.

Output Format


Output T lines, one corresponding to each test case. Since the answer
can be really huge, output it modulo 1000000007.

Constraints


\$1 \le T \le 10\$


\$1 \le N \le 10\$


\$1 \le M \le 300\$


\$1 \le D_i \le 100\$


\$1 \le x_i \le D_i\$

Sample Input

1
2 3
1 1
2 3

Sample Output

12

Code

I have applied dynamic programming, but am exceeding the time limit in most cases. How can I make it faster? I am also eager to know if there is any other method to memoize because these types of grid problems are asked more often.

```
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;

public class Grid_Walking {
private static String[] n;
private static int moves;

private static HashMap hm;
private static BufferedReader br;

private static String[] s;

private static int dimen;
private static int[] present;
private static int[] dimlen;

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

br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while (t > 0) {
n = br.readLine().split(" ");
dimen = Integer.parse

Naming

The name Grid_Walking is discouraged in Java. You should use GridWalking (without the _). The names hm and br are terrible.

Members

The field br isn't used outside of the main method and you can simply make it local.

Leaking resources

You really should use Try-with-resources to auto-close the readers.

try(InputStreamReader is = new InputStreamReader(System.in); 
    BufferedReader br = new BufferedReader(is)){

to make sure resources are properly closed in all scenarios.

Performance

Here's something you can try. Consider this you're taking \$M\$ steps and have \$2N\$ possible ways to go each step. Assuming for a second that the grid is so large that you never exit, then you have \$(2N)^M\$ different ways to step inside the grid. It might be easier to calculate in how many ways you can end up outside the grid...

Better algorithm hints

Lets look at a simple version of the problem see if we can't find some ideas. Let \$N=1\$ and \$M=3\$ and lets draw the states we can be in, specifically lets count in how many ways we can end up in each cell:

                                      

We start with step zero, there is only one possible state we can be in. Taking one step we can either go left or right so there is one way we can end up in either cell shown under \$M=1\$. From there we can either take left or right from both cells. So there are two ways we can end up back at the starting position and one way we can reach each edge. Try to do the steps yourself you'll see you'll get the same values.

So by now you see how this is going. The number of ways you can end up in a cell is the sum of the number of ways you can end up in the neighboring cells. For \$M=4\$ this would be 1 0 4 0 6 0 4 0 1.

There are two things to note here: First, the sum of all the values in the cells is actually equal to the possible routes you can take with \$M\$ steps. Take a moment to think about it, it makes sense, this is your answer (after applying suitable modulus). Second, notice anything familiar with the shape of the numbers? Yepp, that's Pascal's triangle with zeros injected between each cell! The answer for \$N=1\$ is the sum of \$M\$th row of pascals triangle after cutting off the edges due to the size of the grid (the zeros wont affect the result)!

So solving this problem for arbitrary \$N\$ you just need to generalize Pascal's triangle to \$N\$ dimensions. You can easily do this by using a hyper-cube and using the above realization that:


The number of ways you can end up in a cell is the sum of the number of ways you can end up in the neighboring cells.

I will leave the details up to you to figure out, let me know if you need more help.

StackExchange Code Review Q#111609, answer score: 4