Dynamic programming with large number of subproblems

Dynamic programming with large number of subproblems. So I'm trying to solve this problem from Interview Street:


Grid Walking (Score 50 points)

You are situated in an $N$-dimensional grid at position $(x_1,x_2,\dots,x_N)$. The dimensions of the grid are $(D_1,D_2,\dots,D_N$). In one step, you can walk one step ahead or behind in any one of the $N$ dimensions. (So there are always $2N$ 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 for any $x_i$, either $x_i \leq 0$ or $x_i > D_i$.

My first try was this memoized recursive solution:

def number_of_ways(steps, starting_point):
    global n, dimensions, mem
    #print steps, starting_point
    if (steps, tuple(starting_point)) in mem:
        return mem[(steps, tuple(starting_point))]
    val = 0
    if steps == 0:
        val = 1
    else:
        for i in range(0, n):
            tuple_copy = starting_point[:]
            tuple_copy[i] += 1
            if tuple_copy[i]  0:
                val += number_of_ways(steps - 1, tuple_copy)
    mem[(steps, tuple(starting_point))] = val
    return val

Big surprise: it fails for a large number of steps and/or dimensions due to a lack of memory.

So the next step is to improve my solution by using dynamic programming. But before starting, I'm seeing a major problem with the approach. The argument starting_point is an $n$-tuple, where $n$ is as large as $10$. So in fact, the function could be number_of_ways(steps, x1, x2, x3, ... x10) with $1 \leq x_i \leq 100$.

The dynamic programming problems I've seen in textbooks almost all have twp variables, so that only a two-dimensional matrix is needed. In this case, a ten-dimensional matrix would be needed. So $100^{10}$ cells in total.

With 2-D matrixes in dynamic programming, usually only the previous row of calculations is needed for the next calculation, hence reducing the spatial complexity from $mn$ to $\min(m,n)$. I

The different dimensions are independent. What you can do is compute, for each dimension j, how many different walks there are in just that dimension which take $t$ steps. Let us call that number $W(j,t)$. From your question, you already know how to compute these numbers with dynamic programming.

Now, it's easy to count the number of walks that take $t_i$ steps in dimension $i$. You have
$N \choose t_1,t_2, \ldots, t_M$ ways of interspersing dimensions so that the total number of steps taken in dimension $i$ is $t_i$, and for each of these ways you have $\Pi_1^N W(i,t_i)$ walks. Sum over these to get
$$
\sum_{t_1+t_2+\ldots+t_N=M}{M \choose t_1,t_2,\ldots,t_N}\ \Pi_{i=1}^N W(i,t_i).
$$
Now, the memory is under control, since you only need to remember the values $W(j,t)$. The time grows superpolynomially for large $N$, but most computers have a lot more time than memory.

You can do even better. Recursively divide the dimensions into two subsets, $A$ and $B$, and compute how many walks there are using just the dimensions in subset $A$, and just those in $B$. Call these numbers $W_A(t)$ and $W_B(t)$, respectively. You get the total number of walks by

$$
\sum_{t_1 + t_2 = M} {M \choose t_1} \, W_A(t_1) W_B(t_2).
$$

StackExchange Computer Science Q#4941, answer score: 14