Dynamic programming with large number of subproblems

Problem Detail: 

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] <= dimensions[i]:                 val += number_of_ways(steps - 1, tuple_copy)             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'm not sure how I would do the same in this case. Visualizing a table isn't feasible, so the answer would have to come directly from the recursion above.

UPDATE

Using Peter Shor's suggestions, and making some minor corrections, notably the need to keep track of position in the $W(i, t_i)$ function, and rather than only splitting dimensions into two sets A and B, doing the splitting recursively, effectively using a divide-and-conquer method, until a base case is reached where only one dimension is in the set.

I came up with the following implementation, which passed all tests below the maximum execution time:

def ways(di, offset, steps):     global mem, dimensions     if steps in mem[di] and offset in mem[di][steps]:         return mem[di][steps][offset]     val = 0     if steps == 0:         val = 1     else:         if offset - 1 >= 1:             val += ways(di, offset - 1, steps - 1)         if offset + 1 <= dimensions[di]:             val += ways(di, offset + 1, steps - 1)     mem[di][steps][offset] = val     return val   def set_ways(left, right, steps):     # must create t1, t2, t3 .. ti for steps     global mem_set, mem, starting_point     #print left, right     #sleep(2)     if (left, right) in mem_set and steps in mem_set[(left, right)]:         return mem_set[(left, right)][steps]     if right - left == 1:         #print 'getting steps for', left, steps, starting_point[left]         #print 'got ', mem[left][steps][starting_point[left]], 'steps'         return mem[left][steps][starting_point[left]]         #return ways(left, starting_point[left], steps)     val = 0     split_point =  left + (right - left) / 2      for i in xrange(steps + 1):         t1 = i         t2 = steps - i         mix_factor = fact[steps] / (fact[t1] * fact[t2])         #print "mix_factor = %d, dimension: %d - %d steps, dimension %d - %d steps" % (mix_factor, left, t1, split_point, t2)         val += mix_factor * set_ways(left, split_point, t1) * set_ways(split_point, right, t2)     mem_set[(left, right)][steps] = val     return val  import sys from time import sleep, time  fact = {} fact[0] = 1 start = time() accum = 1 for k in xrange(1, 300+1):     accum *= k     fact[k] = accum #print 'fact_time', time() - start  data = sys.stdin.readlines() num_tests = int(data.pop(0)) for ignore in xrange(0, num_tests):     n_and_steps = data.pop(0)     n, steps = map(lambda x: int(x), n_and_steps.split())     starting_point = map(lambda x: int(x), data.pop(0).split())     dimensions = map(lambda x: int(x), data.pop(0).split())     mem = {}     for di in xrange(n):         mem[di] = {}         for i in xrange(steps + 1):             mem[di][i] = {}             ways(di, starting_point[di], i)     start = time()     #print 'mem vector is done'     mem_set = {}     for i in xrange(n + 1):         for j in xrange(n + 1):             mem_set[(i, j)] = {}     answer = set_ways(0, n, steps)     #print answer     print answer % 1000000007     #print time() - start 

Asked By : Alexandre

Answered By : Peter Shor

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). $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4941